Sounds like maybe you want a SmartList. You could set up the rules to include as many genres as you want. Then add a modifier to shuffle the list. Finally, you could optionally limit the length of the list to a certain number of songs... maybe 100 for example; just to keep the list from becoming really large.
Each time you refresh the list, it should shuffle again and pick (mostly) new songs.
Brian.