Hola,
Da facilidades, crea una seccion en tu web en plan "Enlazanos". En esa pagina facilita el codigo HTML de un link a tu web, si teneis algun "manitas" grafico que os haga banners y botones en los tamaños mas estandards, con el codigo HTML correspondiente. Asi cualquiera con una web solo tiene que copiar y pegar.
Frecuenta paginas y foros sobre musica, participando en mensajes (y de paso dejando tu firma). ¿Conoces webs de otros grupos mas o menos en la misma situacion? Podrias intercambiar links con ellos (si, se que son "competencia", pero mejor que os escuchen a los dos que a ninguno).
Dejame recordar,
www.musikaid.com es la pagina de un usuario de estos foros (lochorui). Es sobre grupos independientes, no se si la conocias, puedes preguntarle al webmaster.
No domino mucho los mp3 ni los programas p2p (emule y compañia), pero si en el mp3 se puede meter una referencia a tu web y "sueltas" el fichero en las redes de p2p, podrias conseguir un efecto de "virus". Normalmente lo he visto aplicado a ebooks, haces un ebook gratuito con links y referencias a tu web. La gente se lo baja con permiso para distribuirlo libremente, la gente lo cuelga en su web, o se lo manda a un amigo. Ese amigo lo ve y le gusta, y visita la web el creador. Se que se pueden editar los tags de los mp3 para añadir informacion sobre el artista, pero no se si se puede poner la url o como lo muestran los reproductores de mp3.
Saludos.
PD: Sobre medios de promocion que no son en los buscadores, creo que es mas adecuado el foro de ebussines.