The answer is still shuffle. Your problem can be broken down in two parts: (1) constructing a list of random labels; (2) assembling the required data structure. Shuffle solves the first part, tutorials (perldsc, perllol) for working with structured data may help you with the latter.

use List::Util qw( shuffle );

my @data = map { [$_, undef] } qw( v1 v2 v3 v4 v5 );

my @shuf = shuffle 0..$#data;

my @tab = map { [$data[$_][0], $shuf[$_]] } 0..$#data;

use Data::Dumper;
print Data::Dumper->Dump([\@data, \@tab], [qw(*data *tab)]);
[download]

Please, if you need help or advice with your programming tasks, post them as new questions in Seekers of Perl Wisdom.