elf-bf-tools is an impressive hack, thanks for the link! To add to your list, you might want to mention that simply parsing C++ is turing-complete; see http://yosefk.com/c++fqa/web-vs-c++.html#misfeature-3 . The short of it is that you have to perform full template instantiation in some cases just to parse code that uses those templates!
As to your point about /dev/kmem, to me that is just another argument against the idea of banning JITs from the kernel. There are already lots of vectors for getting attack payloads into the kernel; the JIT angle only helps an attack if you somehow can make the kernel jump to a specified address but don't have root.