Install Cyanogenmod, or buy a phone with it pre-installed like a OnePlus, then you get "Privacy Guard" in the settings which lets you specify exactly what data apps can access.

Android isn't the problem. Google is the problem.

[edit] As in, you can restrict access to things like location, contacts, calendar etc.