This is ugly, but it seems to "work":

#!/usr/bin/perl -w

use strict;

my %hash = (foo=>1, bar=>2, baz=>3);

print $hash{[keys %hash]->[int rand keys %hash]};
[download]

However, it still creates the "temporary array", it just makes it anonymous, inline, and therefore impossible to reuse (so, you go through all that trouble for no really good reason.) If you plan to, in your code, retrieve random keys more than once, I suggest just keeping the array around to save the cost of recreation. That is, until one of the more perl-gifted monks gives you a better answer than this :)