Tengo la solución. He estado mirando tu tema por internet, ya que me parece muy mala suerte lo que te ha ocurrido. De todas formas una de las cosas que pensé es que en la factura de compra debe de venir el serial, pero supongo que no la conservarás... al caso, esto es lo que encontré:
If you are not using iTunes 7, then connect iPod shuffle to your computer and open iPod Updater 2005-01-11 or later. It will display the iPod shuffle's serial number. Here you can also choose Edit > Copy to put the serial number on the Clipboard.
Efectivamente con este programa el cual puedes descargar de la página de Apple, podrías extraer el serial de tu shuffle sin tener iTunes instalado. Este programa es un actualizador de firmware, pero no hace falta que lo actualices para obtener el serial, lo apuntas en un papel y listo.
Te paso el enlace completo a la información:
http://docs.info.apple.com/article.html?artnum=300618
PD: Si te funciona me debes un jamón