I made a plugin for this, in response to this Quora question.

Randomize Main Loop Order

Plugin on Github: JohnDeeBDD/WP-Random-Order-Main-Loop

Just download the .zip from github, then upload it to your site. Let me know if there are any issues.

Read John Dee's answer to Is there a WordPress plugin that will re-arrange my website posts constantly? on Quora

Code on github.com