Hah, speaking of bigmessofwires: TinyCPU. There's even a readymade PCB for it, though it should also be easily fitted into your existing device.
There's another one I can't recall right now which is loosely based on one of the ARM ISAs. And ARM have an official softcore too, though Zeus only knows what the licensing situation is with that.
/ETA/ Here's one: http://www.actel.com/products/mpu/coremp7/default.aspx#software
/ETA/ And another: http://embdev.net/articles/ZPU:_Softcore_implementation_on_a_Spartan-3_FPGA - which also implements the open-source Wishbone expansion bus. Maybe a hardware implementation of Wishbone fits in with your plans, Grackle?
I look forward to your coredumps, myself, Gorgonops. You have a knack for explaining hellishly tricky low-level stuff in a clear and understandable way.
Considered an SAA5050? Or possibly more useful, its descendant:
