The problem is easy to solve by making 99% of all apps normal apps that don't get any special privileges and don't require any developer certification, and having a certified developer program with heavily locked down run mode for the 1% of high security apps like banking and payment apps. It's not hard to attest unambiguously to the user in some way whether they are running one of these rare secure apps or a normal one, a restricted API suffices but you could also just add an LED for it.

You can't possibly convince me that Google couldn't develop something like that if they wanted to.