For what it's worth, in the streaming music players category, Apple Music does shuffle as you want it. Probably because it is an old(er) media player, just with a streaming service bolted on. (i.e. if you tell it to shuffle, it'll take the playlist, put it in a random order in your queue, then play through every song once.)