Microcontrollers
Here's another couple of CPU possibilities: one from Atmel, and one from Microchip:
First, the South Island Component Centre stocks a bunch of Atmel CPUs, including the $4.77 ATTINY12-8PI, an 8MHz 8-pin micro with 1kB of flash and 6 I/O pins. You can program these with an Atmel port of GCC if you don't like their assembly language.
Second, from Microchip, I can get the PIC12F629 chip, in the guise of the PICAXE-08. Also the 12F675 is available. The cool thing about the PICAXE-08 is that it has an ultra-cheap prototype board to make playing around easier. CPU + board = $15 incl GST. It might need a $10 download cable too. The disadvantage is that it only has 128 bytes of program memory, so only really small programs will fit.