Usa titanium backup, le das menu, batch (lotes) y corre la opción de integrar apps de sistema actualizadas. Esto te debe de liberar memoria interna para apps q se han Actualizado y vienen en el sistema de la stock (como YouTube, Facebook, play store, etc).
Para ver cuál de las apps te está comiendo datos internos que da gusto usa link2SD, mira las enlazadas y ordenalas por tamaño de datos (los datos de las enlazadas se almacenan en memoria interna). Si ves apps cuyo tamaño de datos es mayor al tamaño del apk+dex+lib puedes ahorrar espacio interno moviendolas a la tarjeta sd (no enlazarlas, moverlas a la SD)
Espero esto ayude.