I have just found this random Derangement generator that seems to be faster than other generators :
"An analysis of a simple algorithm for random derangements",
by D. Merlini, R. Sprugnoli and M. C. Verri, in Proc. of ICTCS 2007.
http://www.dsi.unifi.it/~merlini/papers/Derangements.pdf
Here is a Matlab version of their pseudoPascal algorithm , with some minor changes in variable names and the addition of two metering variables nw and nr.

function p = GRDmsv(n);
% Generate a random derangement p(1:n).
% Derek O'Connor, Mar 19, 2011.
nw = 0; nr = 0;
derange = false;
while ~derange
nw = nw+1;
p = 1:n; % start with the identity permutation.
k = n;
fixedpt = false;
finished = false;
while ~finished
r = ceil(rand*k); nr = nr+1;
if (p(r) == k) % Early rejection
fixedpt = true;
finished = true;
else
t = p(k);
p(k) = p(r);
p(r) = t;
end
k = k1;
if k == 1
finished = true;
end
end % while ~finished
if ~fixedpt && (p(1) ~= 1)
derange = true;
end
end % while ~derange
return; % GRDmsv

GRDmsv generates a random derangement p(1:n) using what I call "early rejection"
(the authors call it "early refusal").
The outer whileloop is the rejection loop. The inner whileloop is the FisherYatesDurstenfeld shuffle algorithm which is aborted to the outer loop if a fixed point is
generated.
The authors prove that the expected number of calls to rand is E(nr) = n*(e1) = 1.7183n rather than 2.718n for the pure rejection algorithm and 2n for the Martinez et al. algorithm.
Testing shows that the average number of outer whileloop iterations is
E(nw) = e = 2.718, the same as the pure rejection algorithm, but these loops are rejected early and so complete permutations are not built and then rejected. This accounts for the
lower number of calls to rand.
Here are some preliminary timing results:
Permutation length n = 10^6. Times(secs) averaged over 100 samples
GRDrej (Pure rejection) 0.56314
GRDmpp (Martinez, et al.) 0.29022
GRDsta (R.Stafford) 0.40402
GRDmsv (Merlini, et al.) 0.27693
Dell Precision 690, Intel 2xQuadCore E5345 @ 2.33GHz
16GB RAM, Windows7 64bit Professional. MATLAB Version 7.6.0.324 (R2008a)
See this thread for a discussion on derangement generators.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/302075#820677
Derek O'Connor
