You can actually change any of the query parameters (like the order) by adding them to the url.
For instance, the sample url below would randomize the posts on the category archive every time you refreshed, randomizing the results.
http://sample.com/category/uncategorized/?orderby=rand
Below is a basic form with the orderby value that would refresh whatever page/template it shows on. (you would just need to add it to archive.php in your theme, or to the sidebar via an HTML widget)
<form method="get">
<input type="hidden" name="orderby" value="rand" />
<input type="submit" value="Randomize" />
</form>
You would just need to work out the ajax to refresh the HTML element holding your loop. (the guy over at this post is doing a ajax comment refresher, you could look at how he is reloading his loop via ajax