It might be possible to do only one pass through the hash using a technique like finding a random line from a file when the number of lines in the file isn't known.

What... like this :-)

sub random_key {
    my $hash = shift;
    my $line = 0;
    my $match = undef;
    while (my ($key, $value) = each %$hash) {
        $match = $key if rand($line += $value) < $value;
    };
    return($match);
};
[download]

Update: removed unnecessary inner loop.