Lo mejor es instalarte la ROM que quieras sin gapps (las aplicaciones de Google) y en su lugar instalas
NOGAPPS, que son las aplicaciones de Google pero de código libre, que aunque no tienen la mismas funcionalidades que las originales no te espían ni están consumiendo ancho de banda y batería en todo momento.
Yo uso el BlankStore y se pueden instalar/actualizar aplicaciones del Google PlayStore sin problemas, las únicas que no se pueden son las de pago, para esas puedes usar
Aptoide by the face, aunque hay que tener cuidado no vayan a tener una sorpresa dentro que es precisamente lo que se quiere evitar.
Quizás algún programa necesite alguna funcionalidad de las gapps y no te funcione, pero en mi caso van todos, también hay otros stores como
1mobile y
f-droid que son de plena confianza.
Si quieres aumentar tu privacidad (porque no sólo Google intenta obtener datos personales) puedes usar
OpenPDroid (requiere parchear la ROM o usar una ROM que lo tenga integrado) que permite configurar aplicación por aplicación a qué tienen acceso, por ejemplo, hay muchos programas que obtienen tus coordenadas GPS y son una simple calculadora, pues podemos denegarle ese acceso o generar unas coordenadas aleatorias cada vez que lo pida, así el programa sigue funcionando como si nada pasase.
Algunos programas tienen permisos para poder activar y desactivar la wifi y así puedes controlar esos accesos, incluso puedes denegar el acceso a conectarse a la wifi al programa de configuración (setup) de Android.
Es muy completo, puedes denegar el acceso a la cámara de fotos, grabar voz, Device ID, llamadas de teléfono, SMS, etc.
Otros programas imprescidibles serían el cortafuegos
AFWall+ para dejar que sólo se conecten a internet los programas que nosotros queramos (los programas pueden recopilar información pero nunca se enviará a un servidor de internet, además evitamos que se muestren anuncios) y
AutoStarts para controlar qué programas se autoejecutan, por ejemplo, hay muchos que se arrancan cuando activas la wifi.
También podemos usar
AdAway para quitar los anuncios en programas que necesiten internet para funcionar, porque los anuncios es otro coladero a nuestra privacidad.
Evidentemente para controlar todo esto es necesario rootear el dispositivo y requiere cierto nivel técnico manejar estos programas, pero puedes dejarte un Android bastante seguro.