Are there fully working Bitcoin wallets for Android, iOS and Windows Phone (true trustless wallet with sending capabilities)?
Maybe this is what you want.
https://play.google.com/store/apps/details?id=de.schildbach.wallet
I don't think it would be realistic to run the full blockchain on a phone so the kind of wallet he is thinking of would have to talk back to a version of the bitcoin client running on a computer you control. I suspect this one, like Mycelium, talks to a server hosting the blockchain.
(Though with Mycelium, at least, the transaction signing does occur on the phone so it should be safe for certain values of safe)
https://www.circle.com
http://www.coindesk.com/circle-launches-mobile-apps-ios-android/
US only at the moment and the best thing is your btc is insured