Auxio music player[1] for Android shuffles a new order each time the shuffle button is clicked (and ime is excellent for handling well-tagged libraries).

foobar2000 for Windows also changes the shuffle order but (at least in earlier versions) only after a relaunch.

[1] https://github.com/OxygenCobalt/Auxio