Show post in random order

one possibility:
create a category template (copy of category.php, or archive.php if the former does not exist)
http://codex.wordpress.org/Category_Templates
and try to add a line before the beginning of the loop:

<global $query_string; query_posts( $query_string . '&orderby=rand' ); ?>

http://codex.wordpress.org/Function_Reference/query_posts#Usage_Note

same principle – add &orderby=rand

example:

<?php $recent = new WP_Query("cat=-67&showposts=12&orderby=rand"); while($recent->have_posts()) : $recent->the_post();?>