You could shuffle the array normally and check that no element remains in its place, and I think that wouldn't be so inefficent either, as IIRC the probability that no element remains in its place is 1/e, so this would require only 3 shufflings on average.