What I expect from a music player is to play all my songs in random order, such that once a song has been played, it is not picked again until all songs have been played.

There is a difference between randomly picking an element from a list and reordering a list in a random order. This is not a matter of how random really are the random numbers.