Hey,
I've not been around here for a while (I was under a different username before), but I thought you might be interested in my recent developments with generating RGB video (over scart). I posted some pictures on my blog:
http://www.andybest.net/2008/07/generating-rgb-video-with-the-arduino/
If anyone is interested, I can clean up the source code and post it here.
EDIT: I should probably add that my goal is to produce a TV serial terminal with the Arduino
damn that's interesting! I'd really like to see some source code and schematics, if possible ^^
great stuff 
would love more info :3
I'm also interested in your progress!
Apologies, I should probably have the source up tomorrow- I had to reinstall everything on my laptop after getting it repaired
I should probably add that my goal is to produce a TV serial terminal with the Arduino
Fine aim but I doubt if you will be able to do it. I notice that you have done the slow stuff (vertical blocks) and that has tied up most of the processing capacity. To do more you will have to add some extra hardware like a character generator ROM feeding a shift register clocking out your serial video. You will also need a line counting routine to make sure you feed the right data to the ROM at the right time.
With only 1K of memory free in the arduino there is not room for many characters in the display, and you will have to adopt a teletext style of control if you want the characters to be in colour.
The other problem will be the flashing or flickering of the display when a new character is received to display, as this steels cycles from the main job of refreshing the display. Scrolling will also be difficult. The old ZX80 computer used to blink whenever it scrolled for exactly the same reason.
Best of luck.
Well, funny you should say that, but ultimately (more ultimately than a character gen) I am going to use it to generate a pixel clock for the graphics hardware that I have been designing for a Z80 based computer I want to build. I will use a system similar to what you are talking about- but I plan on having a character rom controlled by the data lines of an SRAM.
However, I have seen a project where a full serial terminal has been produced with an atmel device. I'll try and dig it out.
There are 832 cycles available during each horizontal scanline for producing pixels. If you wanted 4 cycles per pixel, this would allow for a horizontal resolution of 208. Of course, you would need to use these cycles creatively in order to get anything worthwhile out of the device.
Anyway, as I said, my plan is to use it to generate some kind of pixel clock for my hardware. Probably at a resolution of 256x288