Major overhaul needed
Android's permission model needs a major overhaul. There is some evidence to suggest that Google was working on small improvements (see App Opps which appeared in 4.3/4.4) but they later disabled the functionality.
There are three main problems:
1. The permissions are not nearly fine-grained enough.
2. Android doesn't provide a sensible framework for withholding permissions at installation or other times.
3. There is a culture of "roll your own camera / phone dialler / text messenger / QR code reader / etc" rather than using the Android intents system, and users don't realise they should complain about it.
The best example of the first problem is probably READ_PHONE_STATE. It allows an app to read not just your phone state (i.e. in a call or not in a call), but also your IEMI, mobile phone number, mobile phone provider, and the mobile phone numbers of other parties if you're in a call. This is required by almost every game and app in the play store. That's a lot of apps which I have to give my phone number if I want to use. This should have been split into several separate permissions; READ_CALL_STATE, READ_IEMI, READ_DEVICE_UUID, READ_PHONE_IDENTITY, and READ_CALLER_INFO. In this case, READ_DEVICE_UUID would be relatively benign (they wouldn't have the IEMI but just a randomly generated device specific UUID suitable for tracking ads across apps on the device) and READ_CALL_STATE would be nearly completely harmless. However, no game should require READ_IEMI, READ_PHONE_IDENTITY or READ_CALLER_INFO and these should be red flags.
Another example of the lack of fine-grained permissions is that access to the internal/external SD card is pretty well all or nothing; if you can read photos from DCIM/ you can also read anything else which any app has put on there. For example, if an app stupidly stores a secret key somewhere in its "own" folder on the SD card, many other apps can read it. There have been some changes to this recently but it's still far from a sensible system. A much better system though would be if very few apps were expected to need READ_EXTERNAL_STORAGE / WRITE_EXTERNAL_STORAGE, but those apps could then pass file handles to other apps through intents. So, a "file manager" app could read and write any of the files, and then pass a read-only or read-and-write file handle to another app, like a document editor. The document editor would not be able to read/write the files directly, but would need to use intents to receive a file handle from a trusted "file picker" app. That way I know that SillyPhotoEffects app can't go reading things I didn't intend it to. For common things like photo viewing apps, I think the best thing would be if they requested a standard application-defined permission like com.android.filemanager.permission.READ_DCIM, which would allow it to interface with FileManager and effectively borrow its permissions to read the photo directories (but not other files).
The second major issue is that there is no sensible system to disable permissions. If an app is installed, it can in theory expect that all of its permissions have been granted permanently. A better system would be if any permission could be withheld at any time and the application would need to be written to handle this. When an application is first installed, the system could ask the user which of its permissions to enable. Relatively safe permissions could be on by default, and potentially unsafe permissions could be off by default with a warning about possible impact on app functionality. Apps could detect which permissions were being withheld and request the user enable extra permissions if needed (e.g. "ExerciseLogger needs to access GPS to track how far you've run. [Option App Permissions].") If your FunFruitSlicer app refused to work without camera permission you'd realise it was just spyware and use the handy uninstall link from the App Permissions screen.
Having the ability to withhold any permission would also solve the problem of "we'd better ask for every permission in version 0.1 in case we want to do XYZ some day." You never know when your government medicare app might need to start taking photos, apparently. Instead, developers could add new permissions to their app manifest with any future update without blocking the update path; they would just be withheld until manually enabled by the user (which the updated version of the app could kindly ask the user to do).
The last problem is really obvious with apps like this Department of Human Services. Almost no apps actually need direct access to the camera or phone dialling or text messaging. If they want to have a photo of something, they don't need the CAMERA permission; they can just use the MediaStore.ACTION_IMAGE_CAPTURE intent, which fires up an app which actually does have the CAMERA permission and which will return a photo to the calling app after (if) the user takes the photo. Similarly, if they want to place a phone call, the app doesn't need any permissions, it should just use ACTION_DIAL which will open a dialler with the given phone number and wait for the user to initiate the call.
The problem with this culture of permission creep and "roll your own X" is that users now believe it's perfectly normal for apps to request 20 different permissions, rather than for them not to need most of those permissions when the intent system works just as effectively. Fixing this issue is the hardest because it involves changing users' expectations, but if the architectural problems are fixed first then hopefully over time people will learn to push back against apps that ask for more than they need.