Yo uso Google Play Music.
Puedes almacenar hasta 20 mil canciones de manera gratuita. Y puedes subir las que tengas ordenadas en itunes automáticamente con el upload manager.
Puedes elegir entre escucharlas en streaming, que se guarden en caché o descargarlas para tenerlas offline en tu móvil o pc (esto último con ciertas restricciones si lo haces desde la web).
El problema, por lo que no le gusta a mucha gente, es que cuando las descargas en el móvil las dejas de tener perfectamente etiquetadas, y se te descargan con nomenclaturas genéricas. Pero yo uso la propia aplicación de Play Music y lo tengo bien ordenado.