As chromatic wrote, you should use the Fisher-Yates shuffle.

However, you said splice wouldn't work for you--I'm curious as to why. What was your code, using splice? I tried this:

while ($game_hand < 12) {
    push @hand, splice @deck, rand @deck, 1;
    $game_hand++;
}
[download]

and it worked for me.

This is, in fact, the very same algorithm that perlfaq4 warns against using.

So use the Fisher-Yates shuffle to shuffle your array.