=Michael B Greenwald
Oops... not a big deal, just needs a minor tweak. The red people (the smaller group, always even) choose first. In the odd case one name remains in the green hat.
So far I follow...
Reveal it, add it to the red hat, and have that green person choose first, redrawing to avoid self-assignment.
Sorry, I'm pretty lost at this point. I think what you are describing involves, midway in the process for odd N, having a single element which has a tiny chance of picking itself, thus requiring a redraw in those rare cases. That's workable (though of course doesn't uniformly generate all derangements nor n-cycles).
(Incidentally, the spirit of this problem (i.e. keep this as "natural" as drawing names from a hat and not using "computation") seems UN-natural to me. PDA's are common enough to assume that some computation device (cell phone?) will be present.)
It's not the computation that I find unaesthetic so much as the intrusion of the omniscient outsider, whether it's a computer, a waiter or a guvmint key escrow officer. You may prefer to think of this as a crypto puzzle akin to an N-way public key digital signature swapfest with no central trusted server (even if it is only a PDA!<;-). But hey, maybe there's a commercial opportunity here to provide Secret Santa software for cell phones!