Good luck, Matt.
I used to write 8051 based code for multi standard cable TV settops. The colour side of things is very complicated, and I agree with the other replies that external electronics are your best option. As Steve said, Philips do a wide range of teletext generators and on screen text drivers and the like with MCS-51 cores, and I think they should be your first port of call. However, you may have difficulty driving a non standard display resolution (unless they have brought out something appropriate since I last looked)
If you want to know more about colour TV statndards, try
http://www.us-epanorama.net/video.html
There is some unseful stuff in there
Hope you get it running!