my $elt;
$elt = $one[rand @one] until $elt and not grep $elt eq $_, @two;
[download]

Update: Use a hash instead of grep for speed.

my $elt; 
my %hash; 
@hash{@two} = (); 
$elt = $one[rand @one] until $elt and not $hash{$elt};
[download]

Examples assume your two arrays are named @one and @two.

-sauoq
"My two cents aren't worth a dime.";