That's the thing, all these holes need to be identified and plugged up. Google, despite being a data-hungry targeted advertising company, did a fairly good job at this in recent Android versions.

Or, a much, much simpler solution: an application firewall built into the system. With downloadable easily shareable rulesets. No matter what an app collects, it's all worthless if it can't send that back to advertisers. We already do that for websites by using ad blockers.