=Eugene Salamin Divide the problem into two stages. First, secretly assign numbers to people by drawing sealed numbers from a hat. Second, generate a random derangement; this need not be done secretly.
This sounds promising, but on further scrutiny, I just can't see how to make it work. Exactly who are which assigned numbers secret from? How do you (and only you) just learn which is your assigned recipient? If you know your own number you can also inadmissibly see who your own Secret Santa is. On the other hand if you don't know your own number how do you select the right recipient assignment from the derangement? Of course an omniscient computer (or waiter) wouldn't have these problems, but we're trying to avoid that device.
Here is one way to generate derangements with equal probability...
Apart from the above issue, as Dan Hoey points out, this particular scheme might paint itself into a corner. But surely Knuth or somebody has a nice deranging algorithm. Anyway, if the derangement's public knowledge then in principle you could just draw one randomly from a deck of prepared cards or something, it doesn't matter. Surely there's a way to do this?!