I think the key is to get a random element in the first position, and repeat the process (recursively) with the rest of the list. IMO the easiest way to do this without side effects is simply to do a random "cut" of the array, and generate a new array from the swapped portions:

sub maybe_functional {
  return unless @_;
  my $n = int rand @_;
  my @arr = ( @_[$n .. $#_], @_[0 .. $n - 1] );
  return ( $arr[ 0 ], maybe_functional( @arr[ 1 .. $#arr ] ) );
}
[download]