Lo que hice y que realmente me solucionó fue:
En primer lugar, utilicé twrp . Antes de la mano estaba usando clockworkmod que no estaba funcionando muy bien. (IDK por qué).
Tengo un Galaxy Note 2 e instalé la ROM CWM 13 Marshmallow y junto a ella instalé el BANKS Open GAPPS.
No he podido entrar en Google. El Gmail funcionaba pero no podía iniciar sesión en nada de Google especialmente en Google Play. He descargado y desinstalado los servicios de Google Play como mil veces.
PARA SOLUCIONAR FINALMENTE MI PROBLEMA, he rooteado mi dispositivo (si no lo está ya, necesitas Rootear) también cada vez que haces un reset de fábrica necesitas re-Root.
Entré en MODO RECUPERACIÓN en TWRP y fui a INSTALAR. Elegí la ROM CM13 y el BANKS OPEN GAPPS que ya tenía en el dispositivo. Básicamente lo reinstalé. Quieres "SWIPE TO FLASH BOTH". Limpia tu DALVIK/DATA. IMPORTANTE: ¡No arranque entre el flasheo de la ROM y el flasheo de GApps!
Tu dispositivo debería reiniciarse después de esto. Debería funcionar después de esto sin que tengas que instalar Servicios ni nada.