Como já foi dito nos comentários, você pode fazer isso com bastante facilidade usando mpd e mpc :
mpc listall | shuf -n 1 | mpc add; mpc play
-
mpc listalllistará todas as músicas conhecidas do banco de dados de músicas -
shuf -n 1(decoreutils) imprime uma entrada aleatória dessa lista -
mpc addadicionará essa entrada aleatória à lista de reprodução atual -
mpc playcomeçará a ser reproduzido (ou não fará nada se o mpd já estiver sendo reproduzido)
Embora mpd e mpc sejam aplicativos de console, também há algumas interfaces gráficas de usuário disponíveis.