Actually check out Coinomi -- the recovery seed is a mnemonic phrase that is not stored on your phone or android device -- they recommend storing on an offline device and paper -- without that phrase your wallet is bricked.

Someone has to have physical control of your phone because there is literally no central account, and all keys are stored on the phone itself -- just like a hardware wallet