Los datos se suelen guardar en carpetas que se instalan en la parte que no se toca cuando se cambia la ROM.
Por lo que hace pelijilla es lo más sensato y más fácil.
Yo también lo hago como "peli". Hace tiempo me comía la cabeza con programas tipo titanium, pero los " destrozos" ocasionados eran peores que los beneficios.
Solo ciertos programas no guardan sus datos. Mira cual de ellos es e intenta hacer un backup fuera de él.