How should one try verifying to whom a given Bitcoin address belongs? Lets say, I'd have a website that shows a large number of Bitcoin public addresses, and wanted to give option for anyone that owns a given address to verify it automatically.

Assuming that one shouldn't trust anyone on the internet based just on their word, how should one go about verifying that a person owns a given address? (methods that can run autonomously, without admin input, are preferred)
The v0.5 client (still experimental as of time of writing) supports a function where you can sign a text message with a private key.  

So you could:
a) have a "register" button next to the address.
b) provide the user a message to sign which includes some identifying information (account name, email address, etc) and the address.
c) user will run bitcoind signmessage  ""
d) this will sign the message with user's private key.

Only a user which has access to the private key that corresponds to the address in question will be able to generate the correct signature.  Think of it as similar to a Bitcoin transaction but it isn't published to Bitcoin network and involves any text message.

Eligius uses this method to link NMC payment addresses to BTC payment addresses for his pool.

http://eligius.st/

Obviously this will have more value once Bitcoind v0.05 is publicly released.