You can easily modify your shuffling procedure to give you a shuffle in which no position remains fixed (this is called a derangement):

sub fys {
    my $arr = shift;
    my $i = @{ $arr };
    while ( $i ) {
        my $j = int rand $i;
        @$arr[$i,$j] = @$arr[$j,$i];
        --$i;
    }
}
[download]

With this change, then all you need to shuffle the columns is this:

@nums = map [ @{$_}[@cols] ], @nums;
[download]

The problem with this simple solution is that it cannot generate all possible derangements. For example, the modified FY misses the derangment 1,0,3,2 of 0,1,2,3.

I looked online for algorithms to fairly sample the space of all derangments of an input list, and the best I found was based on using the standard FY until a derangement is found (i.e. a rejection method). If you need to randomly sample from the space of all possible derangements of the columns, then keep your original FY procedure, but modify the creation of @cols to this:

my @cols = 0..11;
do {
  fys( \@cols );
} until is_deranged( \@cols );
[download]

where

sub is_deranged {
  my $arr = shift;
  $arr->[ $_ ] == $_ and return for 0..$#$arr;
  return 1;
}
[download]

The probability of getting a derangement from a random sample of permutations is ≈ 1/e (i.e. about three trials required per derangement, on average). Moreover, one can optimize the FY procedure around this problem (by having it automatically restart when it encounters a "trivial" swap, i.e. $i == $j), which obviates the need to have a specific rejection step. Therefore this approach has essentially the same time and space growth properties as FY.

Update: Added the stuff about fair sampling, and the rejection method for obtaining a random derangement.