As far as I know all clients allow signed messages, except for maybe a couple of online services. Not even sure of that, since I know you could do it with Empty Gox and that you can with Blockchain.info. I think I can do it from Coinbase as well, though I haven't checked since I only use them as an exchange.
At any rate, if you can prove your address to Wizkid's satisfaction, I'm sure he can arrange something. I'd contact him.
Android's Bitcoin Wallet doesn't sign messages.
Mine does, what client are you using? I'm using Mycelium. If you are referring to the generic "Bitcoin" app, you probably shouldn't be using that one, let alone mining into it. It's very insecure and lacks PIN support, wallet differentiation, standard wallet import/export, and a ton of other functionality I would consider a "must" in a wallet. on-device encryption being really high on my list. Mycelium is also a lot easier to use. Oh, and Bitcoin for Android doesn't support the new wallet format (base-58) either, so it's not terribly useful outside of itself.
Why did you choose that wallet over a more secure/featureful/easy-to-use one like Mycelium? For reference, I use a combination of cold storage (paper) wallets (mining), hot wallets on my laptop in Armory, and a liquid wallet with a small balance that's available both in Armory on the computer and Mycelium on my phone, which is the only wallet I spend from.