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 pseudo-Pascal 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 = k-1;
          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 while-loop is the rejection loop. The inner while-loop is the Fisher-Yates-Durstenfeld 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*(e-1) = 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 while-loop 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 2xQuad-Core E5345  @ 2.33GHz
16GB RAM, Windows7 64-bit 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