Why not just

while (@my_bag > 0) {
        $x = int(rand(@my_bag));
        print splice(@my_bag, $x, 1) . "\n";
}
[download]

This avoids the problem that Skeeve has pointed out.