Here's the approach I wanted to code up, but I've been sufficiently distracted.
The number of derangements is d(n) = (n1)( d(n1) + d(n2) ), and there is a combinatorial proof of this at the wikipedia article. That is, there are (n1) ways to build an nderangement out of a (n1)derangement, and (n1) ways to build an nderangement out of a (n2)derangment. Furthermore, these correspond uniquely to all the ways to build an nderangement.
So here is a way to randomly generate an nderangement:
 Recursively generate either a (n1)derangement or (n2)derangement, with probabilities relative to d(n1) and d(n2). The base cases are d(1)=0 (no ways to generate a 1derangement) and d(2)=1 (only 1 choice for a 2derangement).
 Randomly pick one of the (n1) ways to generate an nderangement from the one you have, according to the combinatorial proof.
Unfortunately, I don't have any time to code this up, and the combinatorial proof is not written well. For the case of making an nderangement out of an (n1)derangement, you simply add n to the end, and then swap the last position and a randomly chosen other position. I couldn't quite understand exactly what the wikipedia article was getting at for the other case, though, and it's been too long since I've thought of such things.
Maybe some curious monk can work this into usable code. But this approach is basically recursive: take a random starting derangement and choose a random way to augment it into a larger one. The end result will certainly be randomly distributed, provided you handle the (n1) and (n2) cases with the appropriate relative probabilities..
All I managed to get into code was a simple routine to count d(n). It uses a different combinatorial identity that is more amenable to simple computation. It seems like you'd need this to get the relative probabilities for the (n1) and (n2) cases to work out:
sub num_d {
my ($n) = @_;
return 1$n if $n < 2;
my $d = 0;
$d += (1)**$_ + ($_1)*$d for 2 .. $n;
return $d;
}

Are you posting in the right place? Check out Where do I post X? to know for sure.

Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>

Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).

Want more info? How to link or
or How to display code and escape characters
are good places to start.