I could also use List::Util's shuffle() and continue to swap and elements that remain in their original positions until all are swapped - but that's seems clumsy.

I have the feeling that would introduce some bias - which may not be important for your problem.