I stumbled upon a site where they sell all kinds of electronic video/audio instruments. There's a lot of interesting information about how these guys managed to get the video output running.. They use a ARM7TDMI Microcontroller in conjunction with an AD725 RGB to PAL/NTSC encoder IC from Analog Devices. They run a crystal at 4 times the video burst frequency to get stable output, it still only handles 256 colors at a 160 x 128 resolution. But it looks like lots of fun to play with, it could also be interfaced with an arduino board. Programming the microcontroller itsself requires C skills and the GNU toolchain, a flash utility and an USB board (i bet the arduino can also be used as an Serial/USB interface to program this board).
http://www.critterandguitari.com/catalog/index.php?main_page=product_info&cPath=1&products_id=13