I don't know how this flew under my radar for so long (probably because I don't read slashdot). Ksplice allows automatic kernel security updates without rebooting. It's a commercial service, but it's dirt-cheap (free in some cases).

From Wikipedia:

Ksplice can apply patches to the Linux kernel without rebooting the computer. Ksplice takes as input a unified diff and the original kernel source code, and it updates the running kernel in memory. Using Ksplice does not require any preparation before the system is originally booted (the running kernel does not need to have been specially compiled, for example). In order to generate an update, Ksplice must determine what code within the kernel has been changed by the source code patch. Ksplice performs this analysis at the ELF object code layer, rather than at the C source code layer.

To apply a patch, Ksplice first freezes execution of a computer so it is the only program running. The system verifies that no processors were in the middle of executing functions that will be modified by the patch. Ksplice modifies the beginning of changed functions so that they instead point to new, updated versions of those functions, and modifies data and structures in memory that need to be changed. Finally, Ksplice resumes each processor running where it left off.

I can't really describe the feeling I get when I read that, except as "FUCKING AWESOME". Okay, maybe fit the words "robot sex" in there somewhere.