The problem now is, if some app requests access to my contacts, it will not only gain access to them but also the ability to upload them to some shady service.

This alone is the reason I will not use Android 6 before they either change this or there is a good firewall available (and I am able to root my device)