Random post in random category

Not sure if this matches what you want but it is a start:

<?php
//get random term, and random posts in that term
$min_count = 4; //minimum number of posts in term to consider
$taxonomy = 'category';
$param_type = 'category__in';
$term_args=array(
  'orderby' => 'name',
  'order' => 'ASC',
);
$allterms = get_terms($taxonomy,$term_args);

// only terms that meet our $min_count
if ($allterms) {
  $terms=array();
  foreach( $allterms as $term ) {
    if ($term->count >= $min_count) {
     $terms[]=$term;
    }
  }
}

if ($terms) {
  $random = rand(0,count($terms)-1);  //get a random number from 0 to number of elements in $terms array
  $term=$terms[$random];
  $args=array(
    "$param_type" => array($term->term_id),
    'post_type' => 'post',
    'post_status' => 'publish',
    'orderby' => 'rand',
    'posts_per_page' => 4,
    'caller_get_posts'=> 1
    );
  $my_query = null;
  $my_query = new WP_Query($args);
  if( $my_query->have_posts() ) {
    echo 'List of Posts in '.$taxonomy .' '.$term->name;
    while ($my_query->have_posts()) : $my_query->the_post(); ?>
      <p><a href="<?php the_permalink() ?>" rel="bookmark" title="Permanent Link to <?php the_title_attribute(); ?>"><?php the_title(); ?></a></p>
     <?php
    endwhile;
  }
}
wp_reset_query();  // Restore global post data stomped by the_post().
?>