I had this problem with my Gen 5 iPod. I accidentally discovered that when the song is playing in cover view (large album image at top of screen) you can just scroll up (so the screen images disappear upwards) to reveal both the Shuffle and Repeat buttons. Press Shuffle here and that's it. Further down beyond the buttons you'll see your song list in random order.