Out of curiosity, because it just seems like you ought to be able to do what you want to do, I searched and found Playlist ordering with 4G shuffle NOT pos… - Apple Community, which, without having an iPod to test with, seems to present a couple of viable options.

More: I just looked at iPod Shuffle (4th generation) in Mactracker and found

"CONTROLS AND ACCESSORIES

Controls  Control pad, Shuffle/Play in order/Turn off, VoiceOver"

Hope this helps.