The technique you're looking for is called a shuffle. It can be done very quickly (linear time IIRC) using standard algorithms. You can try Algorithm::Numerical::Shuffle or List::Util's shuffle function.

If your data is very large, consider sorting a list of numbers corresponding to array indices, then using those numbers as array subscripts. It will avoid making a copy of your data.