The brute force solution:

/bin/perl -w
use strict;
my %h=( k1 => "v1", k2 => "v2", k3 => "v3"); 
my @keys= keys %h; 
my $k= $keys[int rand( @keys)]; 
print "random key: $k\n";'
[download]

If you want to do this on a huge hash and you want to do lots of random access and updates then you should look at Building a Better Hash, a pretty clever way to solve this problem.