Apps on Google Play are throughly infested with ads and analytics and whatever. On desktop we used to call this kind of applications "spyware", frown upon them and let antivirus software block those on sight. On tablets, this is a norm of life.
Some guys from Cyanogen released a proof on concept a while ago. You could install any Android app and select which permissions to "mock".
Anyway, I think the permission system in Android makes sense the way it is. It forces app developers to declare what they want to do on you system, but the install process stays simple and straightforward. On Windows and OS X, we used to give every app the "do whatever you want with my computer" permission for years.
On Android you risk a shitstorm of bad reviews if you fail to explain the reasoning for permissions to users. And Google can use the permission list and double check apps with critical permissions for malicous behaviour.
First off, there are already lots of places you have to handle compatibility based on the version of the phone, intents available from other apps installed on the phone, or capabilities (even something as basic as a phone can't be guaranteed if you support tablets).
Obviously you can turn small things on and off in a block of code with if statements, but you can handle major changes with the Fragment model. If you have a drastically different UI due to a missing intent/permission/API feature you can actually ship the app with 2 different Fragments and decide which one to show at runtime.
As an aside, I turned off auto-updating for Facebook and will not upgrade from here. Too many permissions, too intrusive to the UI. I have deleted Facebook from my phone before and I'm fine without it now.
Of course this would soon be a cat and mouse game if Google really implemented it for everyone: Developers like WhatsApp would check the address book data whether it is statistically sound and if not they would request you to grand access for real, etc.
All the permissions only required for ads (like position, IMEI, full internet access, reading sms, reading address books) would also just have the app terminate if it's not possible, just like today they check for rooted devices based on tools like bash or they check for modified hosts files that block ads.
It is almost unavoidable that this happens. As Android is used more in enterprise settings, permissions such as access to contact databases would have to be selectively granted, and controlled by mobile device management systems.
It should always be the user's or administrator's choice. There really is no such thing as a "core" permission. Of course some apps become a nullity without some access, but an unhandled security exception in those cases could result, for example, in a more-detailed system message asking if you want to uninstall the app, since you have decided against giving it permissions that the developer has decided are essential. This would also alert you to when a non-location app was trying to sneak a look at where you are.