Собственно вот мой скрипт:
sbin.ru/radio.zip
Он был даже двух версий, внутри обе с примером запуска (бесконечный while т.к. иногда под нагрузкой мой старый сервак не справлялся с процессом и коннект рвался).
Для запуска нужен icecast, perl-модуль Shout, а также вот это
sbin.ru/mp3tools-27-11-05.tgz (на x86_64 могут прилично глючить, потому что писалось это в 2003-2005 годах, а первый amd64 у меня появился в 2006 году).
Рандом по списку был сделан так: выбирался случайный элемент, выкидывался из списка, а следующий выбирался на расстоянии между cur_list_length/2 и cur_list_length от текущего. Это понижало шансы на выбор двух песен одного исполнителя подряд, ведь предполагалось, что исполнители в файле сгруппированы (у меня они были разложены по каталогам, а список генерировался с помощью find). Реализовать какой-нибудь более умный алгоритм я так и не собрался.