While playing around with my iPhone last night, I found that the 'shake to shuffle' feature will work from the mini-player that pops up on your screen after a double-tap of the home button. To enable the mini player (i.e. the iPod controls), go to Settings » General » Home Button, and select iPod controls.
The only issue I have had was that when I really shake the iPhone, it goes to landscape mode and freaks out.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20090909215330643