Bei der Frage kommt es halt immer an wie du sie lösen willst. Die sauberste wird über OpenPDroid sein.
Was du erwähnt hast geht auch, dazu muss du dir die App auf den PC laden, dekompilieren, die Rechte in AndroidManifest.xml entziehen, App wieder kompilieren, signieren und auf dem Gerät installieren.
Diese Methode hat jedoch einige Nachteile, wie z.B. dass du keine Updates aus dem Play Store mehr installieren kannst, bei vielen Apps kann es auch dazu kommen, dass sie instabil laufen...
Wie das dekompilieren der Apps geht, hatten wir hier schon einige Mal behandelt. Ist halt nicht die effektivste Variante, da du dir so bei jedem App Update die Arbeit von neuem machen musst, bei manches Apps sogar mehrfach bis du heraus hast, welche Rechte du bei der jeweiligen App bedenkenlos entziehen kannst.
Da stellt sich dann eben die Frage, ob eine AOSP ROM mit OpenPDroid nicht angenehmer ist. Am besten du schaust mal in deinem Geräte Forum, ob es so eine ROM nicht schon gibt. Falls ja, teste sie aus und schau, ob es dir nicht genehmer ist.