There's a better permissions system coming in Android Marshmallow, but that doesn't help anyone right now.
In this regard I've had a good experience with Privacy Guard feature on CyanogenMod 11 (based of Android 4.4 KitKat) and later. It allows you to control each app's access to a permission - allowed, ignored (disallowed), or "always ask". The last one triggers a popup whenever an app X wants to user permission Y (e.g. "Skype wants to modify your contacts" - wait what?!) where you can allow or ignorile it, and also set it as a future default to prevent being nagged with the popup. Although I personally very much like the option to opt-in or opt-out, I understand that even Privacy Guard UX is not for everyone. Luckily, you can choose if you need Privacy Guard and activate it per app, or have it automatically activated for every newly installed app with the "always ask" option for each permission.
In practice, the app could ask for permission to use the GPS the first time you use the "running" function, and then spy on your location ever after. The difference is in the perceived privacy.
At least they could have deprecated that system and allowed it to work with old apps, while encouraging new apps to use an iOS-like we'll-ask-when-we-need-it kind of system?
If I'm using the app and discover a new feature that asks me for permission A, I understand why, and can make a reasonable decision.
But the context of me switching to the "running" feature and then I'm asked if I want to allow the GPS function is enough for me to not feel watched. It's all about context.
Same if the app asked for permission to see your photos (forever) when you use the custom cover art feature.
For a malicious app this makes no difference, but for those apps we (sort of) trust, the context makes all the difference.
Permission would be necessary to actually query for media programmatically, which is the real issue. Currently, they are conflated.
For location, I suppose that the "Google Maps is using your location" bar at the top could be expanded and always present when the location permission is enabled. Tapping it would revoke the permission until it is enabled again. This could get annoying though, some apps legitimately do depend on location all the time.
Is this some still-unreleased version of the app the article is about, or has the privacy policy changed with no changes to the data that Spotify actually accesses?