Check out this nifty little iTunes 11 keyboard shortcut Adam Christianson showed me: when you hold down the option key, the back button turns into an insta-Genius Shuffle button. It's that simple, but here's what it looks like:
iTunes 11 in its everyday normal state
Now, hold down the Option Key on your Mac (it might work with the Alt key in Windows, but I didn't have a Windows box handy to test it), and it looks like this:
Insta-Genius Shuffle!
Click that Genius Shuffle button, and you get an on-the-fly playlist that Genius builds around that song. In this case, I clicked the button on "Butterflies," my favorite Atomic Love Bombs tune. When it was over, iTunes went to "Telephone" by The Black Angels, as shown below.
Note that the Genius Shuffle button remains active at this point without the option key. That's to let you know that it's in Genius Shuffle mode.
Look, Ma! No hands!
Also note that this is a live shuffle, rather than a newly-ordered playlist, so it bops around from tune to tune within your normal library list.
This may have been an iTunes feature in earlier versions, but I fear I keep my system up to date and wasn't able to test it on any other version.