How 'bout this for an algorithm:

1. shuffle the list using List::Util's shuffle() routine.

2. swap all pairs of elements that are in their original place.

3. figure out what to do when there's an uneven number of elements in their original place (this shouldn't be hard).