I suppose I am pretty simple minded here. I think it is quite proper for the user to deny internet access to apps which don't seem (to the user) to need it, and if the app really does need it (map program!), it crashes or maybe recognizes the missing permission and exits with a message saying why. If the app only wants it for ads, and the app dev wants to not run without it, that is perfectly fine with me.
None of this seems like a very big problem to me. Users should be able to deny any permissions. App devs should be able to choose any reaction from crashing to detecting and explaining why the permission is needed.
As an aside, I wondered right from the start why Google didn't allow users to tailor permissions for apps.