List::Util's shuffle is good, but it's totally random, so it doesn't guarantee anything about the position of the shuffled elements. A brute-force solution would be to shuffle repeatedly until you end up with a satisfactory order, but that really sucks.
Reading the whole WP entry, you might try a bozo-shuffle -- if it's not shuffled, swap the current item for an item later in the list, then back up 1 position (as the just swapped in item might sort before the previous item).
(This seems to devolve into a bubblesort in reverse, well, sorta.)
-QM
--
Quantum Mechanics: The dreams stuff is made of