I'm going to ignore third party solutions that require root, because those aren't part of the equation for 95%+ of Android users.
Android should have three levels of permissions: Implied (i.e. all apps get these), explicit (at installation), and prompted (user is asked at runtime).
- Implied ("freebies"): internet connectivity, store data, get a unique device ID (per app?), store the app's own accounts within the accounts API.
- Explicit (installation): Run in background, use GPS, use the camera, use the microphone, etc.
- Prompted ("personal information"/"cost you money"): Access your cellphone number, access your contact list, access your calendar, access your email, read/send texts, make calls, etc.
Users in the current Android ecosystem learn to ignore permissions pretty quick as most are for trivial stuff (e.g. internet access, store data on the SD card, store an account, etc).
Worse still a lot of users will skip apps that ask for too many permissions which is bad for both the app developer AND users. Most developers want to offer functionality (e.g. share to contacts) but don't want to do so at the cost of losing users ("Why is this asking to see my contact list?").
Android needs to drop a bunch of "silly" permissions that have no inherent cost to the user. They're clearly created by an engineer who just wanted to slap permissions on every kind of API for no good reason. It benefits nobody.
They then need to take permissions which have a cost (either literally or to user privacy) and set them up rationally so they're either something you get when installing OR something you'll be prompted for.
Lastly Android needs to add a description field to the permissions manifest where the developer can put in a short explanation for why they need permission XYZ. Limit it to 128 characters if you wish. The app store can display these.
I install less apps on Android largely because many ask for too many permissions. If Google makes it really easy for me to protect my personal information (e.g. prompts) I'll literally spend more money on their store because I'll feel more safe to do so. As a developer I'll also offer more functionality to my apps as there is no permission "cost."