Be aware that Fletch's solution doesn't give you an uniform distribution over the array elements if all the arrays don't have the same length. If you prefer that, you can use this :

my $count = do { # or keep track of it yourself while adding your elem
+ents to %hoa
 use List::Util qw/sum/;
 sum map ~~@$_, values %hoa;
};
sub randelt {
 my $i = int rand $count;
 my $v;
 while ((undef, $v) = each %hoa) {
  last if $i < @$v;
  $i -= @$v;
 }
 keys %hoa; # reset hash iterator
 $v->[$i];
};
[download]