Something that may be of help: a substantial fraction of permutations are derangements (that is, permutations where no object stays in its original position). In fact, as n->infinity, the fraction of permutations on n objects that are also derangement, d_n/p_n, approaches 1/e, or about 0.3679, where e is the base of the natural logarithm.
Therefore, any method that can give you a uniformly random permutation, together with a method to check for whether or not anyone left their original chair, can be modified to solve this problem. You simply keep trying until you get a random derangement, and on average, you only need to make e (about 2.7183) attempts. 98.98% of the time, you will find a derangement in 10 attempts or fewer.
EDIT: d_n/p_n = 0.3333, 0.375, 0.3667, and 0.3681, for n = 3, 4, 5, and 6, respectively, so the convergence to 1/e is very fast (note that the ratio is always falling, and hence, approaches 1/e from above), and hence, this technique is always valid.