So having decided to add video, the next question would be: what kind of of output would be necessary to connect to the display? Again there are some choices depending on how much you want to do yourself and how much you want to hand off to a pre-made chip. Making this I wanted to learn as much as possible and do it all myself so I think this really boiled down to three options.

1. Composite video. One signal wire which has the both control values and the actual video data modulated together. Interlaced. Colour is problematic. Upper resolution limit of 10 Mpix/s. One scanline required every ~64 us (512 clock cycles at 8 MHz). Input not present on my TV. Similar restrictions apply to S-Video.
2. YPbPr component video. Three signal wires, with control plus signal combined with the Y signal. Complex encoding. Good image possible; interlace not required.
3. VGA. Not present on most TVs. Good picture quality, high resolutions possible. Easy encoding. Lots of signal pins. 640x480 minimum standard nearer 20 Mpix/s. One scanline in ~32 us.

I chose composite, but if I were to do it again I'm not sure I would make that choice. I have a composite to HDMI adaptor so that removes a lot of complexity (plus I only need to make the signal work with that one device). Also the Arduino tv-out library was an excellent starter for providing the carrier signal. Finally a number of other choices meant higher resolution and bit depth/colour were not relevant to me. Getting composite to work has been challenging enough!

Looking a bit more in depth at these specs, YPbPr would be doable. You would just require the CPU to write data encoded in that fashion directly into memory. I'm not sure what circuit I would use to turn RGB into YPbPr!

VGA is probably too fast for this CPU, assuming synchronised clocks. Or if a double-rate clock was used, the memory would need to be considerably faster. Though to be fair the pixel rate is flexible, but the vertical resolution is not. If the pixel clock were halved we could have 320x480. Or one quarter, it could be 160x480, but these strange rectangular pixels would not be very nice.

Composite it is.