If you turn on shuffle mode on your iPod (Settings > Shuffle > Songs) you can then start playing all the music from a given genre in shuffle mode. Select Music > Genres > [the genre you want to play] > All > All, then select a song.
You can start with the first song (this list is in alphabetical order) or scroll through the list to select any other song. After your first selection, the other songs in that genre will play in shuffle mode.
.
