Generation of text on composite video
What sort of processor and memory system are you using?  Many home computers in the 1980's had the video system that takes data directly from the processor's memory.  Depending upon the processor, it may be possible to have the video system receive data from memory when the processor isn't using it (this was done on e.g. the Apple ][ series); even if that's not possible, having the video receive data directly from the CPU will often allow nicer screen updates than would be possible if the data had to be fed to another chip; one can vary the complexity of the hardware based upon the level of CPU loading that would be considered "acceptable".  Note that if your processor/microcontroller has a spare DMA channel, the level of hardware required may be very slight--especially for a bitmap display--and the CPU may only need to be interrupted once per frame [depending upon the DMA controller, you might not even need that].

It would be possible to use a CPLD along with either a parallel or serial RAM to create a video subsystem which could run mostly or totally autonomously but would allow the main CPU to perform some display updates during the time when the display was blanked (depending upon how much logic you want to put in the CPLD, the main CPU may have to make sure it reset the address on the SPI RAM in time for video to resume clocking).  You could also use a CPLD along with a parallel RAM to emulate a serial RAM; if you were planning on interfacing a serial RAM with your CPU anyway, that might be the best approach.  Since the main CPU and the video would each only need to access two million bytes per second maximum (assuming one-bit video), there should be no problem interleaving the parallel memory cycles.  I would guess that a CPLD with 64 or 72 macrocells could do the job "barely", or one with 128 or 144 macrocells could do the job "comfortably".  I'd be inclined to go with the latter, since it could probably include a variety of features that would greatly expedite display updates (e.g. the ability to automatically bit-shift or mask incoming data).