MP3 players: Mp3 shuffle lacking

Random play is...

...usually written into the firmware. If it's not there now, chances are it will never be there. Most manufacturers won't allocate resources to update an old player...unless they sold millions of the thing. Plus, random (or shuffle) play isn't something that can be manipulated by the song files prior to transferring to the player. How would you? Rename your songs? Your player would still play them in the same order every time. Without random play built-in, your MP3 device chooses to play songs (typically alphabetically by filename, ID3 tag data, etc.), and you're more or less stuck with it.

Your most reasonable solution is to pick up a player that does have shuffle play as a feature.