Mediamonkey allows me to just go to tracks and hit shuffle and then it randomly adds all my tracks to a queue with no repeats. You can do it at any level of hierarchy, allmusic, playlist, album, artist, genre etc.

Edit: I checked I can also shuffle a folder without adding it to the library.