There's also a colour bar generator using a PIC, I can't remember the URL off hand, but I built one a few years back - using a 4MHz 16F84 overclocked at 10MHz.
As Exo said, the way to go is to use an OSD chip - the biggest problem is finding details on them. I used an NEC chip a number of years ago, and Dontronics was going to make a SIMMStick board available using it - but NEC had already discontinued the chip :cry: I tried to obtained samples of the new chip that replaced it, but never managed to get hold of one, so gave up. Then a couple of years later, Don released a SIMMStick board using an ST design by someone else.
I've still got a few of the old NEC chips that I removed from Hitachi VCR's and Amstrad Satellite Receivers - the NEC was the only chip I could find a datasheet for.