Los temas suelen ser solo si eres root, no hace falta un zip para recovery aunque ya esta un poco en desuso tienes app como metamorph (claro que al no usarse mucho esta, escasean los temas para ella), claro sigues necesitando ser root y al termiar si cambias el framework-res.apk reiniciar para que surja efecto (el resto no es necesario).
Si no eres root y no te quieres complicar como mucho y dependiendo del launcher puedes poner temas a este, no cambia tantas cosas como uno completo pero algo es algo, no hace falta ser root y los puedes encontrar en gplay, ahora estan empezando a hacer temas para apex launcher tambien.
Existe una tercera opcion que hace mucho que no veo son temas casi completos por APK los tenias en gplay (por aquel entonces aun era el market) pero ahora los tienes similares aunque la ROM debe estar preparada ser compatible con la aplicacion ThemeChooser (y que este esta incluida en la ROM, claro)