What's your desired process for earning trust?
Of course, there'll be ways around this but it would stop a lot of dodgy apps. Of course, this is a lot harder as it sounds as you'd need all Android apps that want access to sensitive APIs to interact with the Playstore API. But it's better than Android just imposing systemwide security changes that break a load of apps.
Can you sell your trusted account?