user13312: I need to know with 100% certainty that someone can tell me "this is my wallet" and prove it to me.  I could of course simply get their private key/brainwallet phrase, is there any other way to do it?

user-1: Yes. Bitcoin uses asymmetric key cryptography, so the natural approach is to have the user use (rather than reveal) their secret key in a way that can be verified using only the public key. The only disadvantage is that the public key will be revealed---Bitcoin is in a sense even safer than most other uses of asymmetric key cryptography in that this only occurs after a transaction or signature is made from a bitcoin address' private key. But the general idea is that asymmetric key cryptography remains safe if the public key is indeed public (and unless there are big math or physics breakthroughs, such as a large quantum computer, that should remain true).
The most trivial way to do this is to ask the user you want to prove his ownership of a Bitcoin address to move bitcoins from it. If he can comply, obviously he has control over it---or tricked someone else into moving them. So if you are really after 100% certainty, you would have to ask for all bitcoins at that address to be moved to one of your addresses (specifically created only for this transaction), presumably on the promise that you would return them immediately. That is still slightly better than requiring the customer to reveal his private key, which would allow you to take possession of any Bitcoin at that address at any time, not just during this one-time verification. However, the only real advantage to this scheme is that you won't have to explain much because any Bitcoin user will know how to transfer bitcoins, and you can verify that it happened simply by observing the blockchain.
There is another option, signatures, which Meni Rosenfeld has already explained in his answer. Any Bitcoin client will allow a user to create custom signatures, but you may have to educate them about it because it is not a commonly used feature yet. There is a further usability issue in that the signature does not automatically get transmitted, so you have to ask the user to share (i.e. copy and paste it). Finally, you can only verify if the user has signed the exact message you asked him to with the Bitcoin address you expected---there's little you can do to help troubleshoot if it turns out this is not what he did other than to reiterate that you'll need the exact same text with no edits, extra line-breaks, etc.
Despite these practical barriers to using signatures, they have huge advantages, not just that you never do need to be trusted with the bitcoins themselves, but also non-repudiation: You can ask for any kind of statement (such as in Meni Rosenfeld's example), and by signing it, you probably (I am no lawyer, though) achieve non-repudiation, since only people who have the private key to the Bitcoin address used for signing are able to create such a signature. So if anything ever goes to court, the person who signed the statement will find it very difficult to uphold any claim that someone else created the signature---he'd have to either say it is not his Bitcoin address after all, or else that his wallet was stolen but the hacker didn't bother to take his Bitcoin, merely creating this signature instead. Hence you may be able to add extra features---such as providing his identity or agreeing to some contract, at least if your agreement with that other person involves him taking responsibility for keeping his private key private and him assuming liability if anyone else uses it.

user575: Yes, you can use "Message Signing", available in most Bitcoin clients, including Bitcoin core. If I sign with my address the message "I am Meni Rosenfeld and I am proving to user127317 that this is my address", you can be sure it's mine.

13312: <p>I need to know with 100% certainty that someone can tell me "this is my wallet" and prove it to me.  I could of course simply get their private key/brainwallet phrase, is there any other way to do it?</p>
 -1: <p>Yes. Bitcoin uses asymmetric key cryptography, so the natural approach is to have the user <em>use</em> (rather than reveal) their secret key in a way that can be verified using only the public key. The only disadvantage is that the public key will be revealed---Bitcoin is in a sense even safer than most other uses of asymmetric key cryptography in that this only occurs after a transaction or signature is made from a bitcoin address' private key. But the general idea is that asymmetric key cryptography remains safe if the public key is indeed public (and unless there are big math or physics breakthroughs, such as a large quantum computer, that should remain true).</p>

<p>The most trivial way to do this is to ask the user you want to prove his ownership of a Bitcoin address to move bitcoins from it. If he can comply, obviously he has control over it---or tricked someone else into moving them. So if you are really after 100% certainty, you would have to ask for all bitcoins at that address to be moved to one of your addresses (specifically created only for this transaction), presumably on the promise that you would return them immediately. That is still slightly better than requiring the customer to reveal his private key, which would allow you to take possession of any Bitcoin at that address at any time, not just during this one-time verification. However, the only real advantage to this scheme is that you won't have to explain much because any Bitcoin user will know how to transfer bitcoins, and you can verify that it happened simply by observing the blockchain.</p>

<p>There is another option, signatures, which Meni Rosenfeld has already explained in his answer. Any Bitcoin client will allow a user to create custom signatures, but you may have to educate them about it because it is not a commonly used feature yet. There is a further usability issue in that the signature does not automatically get transmitted, so you have to ask the user to share (i.e. copy and paste it). Finally, you can only verify if the user has signed the exact message you asked him to with the Bitcoin address you expected---there's little you can do to help troubleshoot if it turns out this is not what he did other than to reiterate that you'll need the exact same text with no edits, extra line-breaks, etc.</p>

<p>Despite these practical barriers to using signatures, they have huge advantages, not just that you never do need to be trusted with the bitcoins themselves, but also non-repudiation: You can ask for any kind of statement (such as in Meni Rosenfeld's example), and by signing it, you probably (I am no lawyer, though) achieve non-repudiation, since only people who have the private key to the Bitcoin address used for signing are able to create such a signature. So if anything ever goes to court, the person who signed the statement will find it very difficult to uphold any claim that someone else created the signature---he'd have to either say it is not his Bitcoin address after all, or else that his wallet was stolen but the hacker didn't bother to take his Bitcoin, merely creating this signature instead. Hence you may be able to add extra features---such as providing his identity or agreeing to some contract, at least if your agreement with that other person involves him taking responsibility for keeping his private key private and him assuming liability if anyone else uses it.</p>
 575: <p>Yes, you can use "Message Signing", available in most Bitcoin clients, including Bitcoin core. If I sign with my address the message "I am Meni Rosenfeld and I am proving to user127317 that this is my address", you can be sure it's mine.</p>
