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 ACCESSORIESControls  Control pad, Shuffle/
Play in order/Turn off, VoiceOver"
Hope this helps.