my @array = (
    ["foo", 1],
    ["bar", 3],
    ["baz", 4],
    ["quux", 9]
);

@array = sort { $a->[1] <=> $b->[1] || $a->[0] cmp $b->[0]} @array;
my $sum = 0;
$_->[2] = ($sum += $_->[1]) for @array;
my $v = int(rand $sum);
my $idx = 0;
$idx++ while ( $v > $array[$idx][2] );
print $array[$idx][0],"\n";
[download]

If the list was really large I'd think about binsearching the results. And if I didn't care about memory (often there is no need to care), then I'd just duplicate the elements into a list and then use a random index into the list. For instance if the list is small there is nothing really wrong with doing the easy thing...

my @list = map { ($_->[0]) x $_->[1]  } @array;
my $elem = $list[rand @list];
[download]

(RAM is cheap.)