You could also use a variation on the random line from a file FAQ:

my( $key, $val );
my $ctr = 0;
while( my( $k, $v ) = each %hash ) {
  rand( $ctr++ ) < 1 && do { $key = $k; $val = $v };
}
[download]

Actually merlyn's is more efficient since it only reads up to the "victim" element, whereas this would hit all elements (which it has to for the original random line from a file version). Then again if this is a tied hash and FETCH had side-effects that might be what you want. At any rate see perldoc -q "random line" for more info.