While looking for a solution to display characters over video for an on screen display I came across the Maxim MAX7456. This is one easy to use chip for exactly this purpose. Using a SPI bus it is easily interfaced with a PIC microcontroller (I'm using a PIC18F2520 for testing).
I have just started playing with this chip and have discovered how easy and powerful it is to use. I have one project in mind for it that I am starting on now and will post again once it is further developed.