Prova a scaricare es gestore file, dargli i permessi di root e montare tutto come r/w, poi andare su cache -> dalvik cache e da lì eliminare tutto.
Poi prova a scaricare un'app e vedi se ti va.
Facendo questo procedimento, il cell dovrebbe cominciare a darti problemi (dovrebbero crasharti un bel po' di app), però riavviando il cell si aggiusta tutto. Se, come succede a me, le applicazioni te le fa installare, è un problema più di cache che di memoria interna.
A favore del fatto che il problema non è della memoria interna, se installi un app tramite apk quella dovrebbe fartela installare tranquillamente. Se invece la memoria interna fosse limitata, non te la farebbe installare.
Io comunque sto provando a cambiare rom.