Shuffling an mp3 player

I built an mp3 player and am having the toughest time figuring out how to randomly shuffle the songs.

It turns out random() isn't actually random, and will do the same sequence each time. I tried using randomSeed(analogRead(A0)) to at least start at a different song after each power up, but there are surprisingly many repeats, sometimes songs will play three times in a row.

I have 138 songs now, and was thinking of creating an array[137], then picking off each song as it plays, then recalling random() on 137 songs, reducing by one each time.

However, arrays cannot remove positions, I could just set the value to 0, and my concern is that random may not play all the songs, so it will just keep skipping some.

Does anyone have an idea for how to do this?