iTunes 11 removed iTunes DJ (neé Party Shuffle), in which it was possible to queue up a random subset of your library or of a selected playlist, and change the queue with a click of the "Refresh" button. At first it seemed as though this was gone completely, but after some fiddling it appears you can get most of the functionality back as part of the new Up Next feature.
First the basics: Starting from a playlist, just click the shuffle icon (the intersecting arrows) in the header of the playlist view, not the shuffle icon in the iTunes LCD. However, there is no shuffle icon when you view your entire music library, so you'll have to fake it by creating a smart playlist with the condition "Media kind is music," with live updating turned on.
Click list icon at the right of the iTunes LCD to view the Up Next queue. The clock icon in that list shows recently played tracks, like the dimmed portion of the old iTunes DJ interface. You can re-order songs in Up Next by dragging them around, and new items can be added to the top of the queue form anywhere in your library using the contextual menu, just like you could in iTunes 10, or by clicking the > icon that displays when you hover your cursor over a track.
What may not be obvious is how to replicate the function of the Refresh button. To do this, click the shuffle icon in the header of your playlist view again.
Now for the caveats:
Mac OS X Hints
http://hints.macworld.com/article.php?story=20121129135613968