Is it possible for someone to verify that a wallet is theirs wallet, without providing their private key? 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?
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.