Look at the use of CNAME's. Getting users to create custom CNAME's on their DNS records, and having your site try to access these is one way of verifying the ownership of a domain.
Another would be a bit more work, but getting users to add a Meta tag to their site, and again have your page attempt to access and read this Meta information to prove that they have access to the page - Thus verifying ownership.
UPDATE:
dns-get-record