Have a look at this thread: random derangement. Suggestions include:

1. generating a random permutation until you get a derangement (expected number of tries is e), and:
2. using a modification of the basic random shuffle algorithm

It's a Mma mailing list, but I'm sure the algorithms can be translated to perl.

Update: the modification of the basic random shuffle algorithm is to swap position j with a random element from positions j through the end which doesn't violate the derangement condition.