If the problem is lost/stolen phones falling into the hands of mortals the problem is solvable. On boot and inactivity require a PIN/password to access the UI. Encrypt the removable storage if it has passwords or at least encrypt the password files with a key stored in the phone itself, preferably stored in the crypto area of the CPU or in the SIM. On boot don't access the keys until a successful user login. Doing those few steps stops anyone who isn't prepared to get into a stolen phone without interrupting power and hook up to the memory bus without crashing the phone. So unless your opponent is a nation state or seriously funded corporate spy you would be pretty safe.
Oh, and you would also need to enforce signed OS images from trusted sources (i.e. Trusted Computing) for it to be secure against someone just flashing a version of Android that didn't enforce the rules. This problem exists regardless what solution is proposed. Whether it is worth that price I leave to the reader.
A few more precautions in the hardware could close most of the remaining bugs but probably at expenses in bill of materials and user irritation most would be unwilling to pay for. So stop 99% of the problem and leave the 1% for secure MILSPEC hardware.