I second the idea of using a Propeller but I understand if you've never worked with one, it can be a difficult challenge because its native language is something called "Spin" which sort of looks like a simplified version of Pascal with objects. There is a GCC port for the Propeller but because it wasn't designed for C/C++ (it has no stack, for example), the most efficient way to do things with a Prop is to use Propeller Assembler, aka PASM.
Indeed the Propeller is very good at generating (standard definition) video signals, even if the main clock frequency is at a totally different rate than the video frequency. The disadvantage is that it has only digital pins, so an analog video signal is simulated by using resistor networks that serve as D/A converters. Also, with only 32KB of "hub RAM" on board, the screen size for a graphics screen would be limited, so most video drivers use "tiles" in the same way as the Commodore PET or the UK101/Superboard used graphics characters.
There are many tricks to work around problems such as pin shortage or RAM shortage. For example, you could design a system where the Propeller generates the hsync and vsync signals but where a large SRAM chip stores the pixels. The SRAM could either be mapped into the 6502 address space somehow (which would require clock synchronization so that the pixels are extracted to the video generator during Phi1 when the 6502 doesn't use the databus) or you could design a system that's similar to the TMS9918A chip that was used in MSX systems to generate video by way of indirect commands. I know cbmeeks knows more about those.
In my
L-Star project, I use a video driver from the Parallax Object Exchange (which is where Propeller enthusiasts can post their software to share) which uses a trick to generate a monochrome video signal with only one digital pin: it generates a high-frequency PWM signal to simulate the "black" level in a video signal, and it sets the pin to LOW for sync/blanking and HIGH for white.
I've also thought of using Teletext decoder chips for video output. They are still available on places like eBay, and on a Propeller it would be trivial to generate a monochrome video signal with Teletext information in it. In fact it would be possible to generate up to 7 Teletext streams (one per cog, plus an eighth cog to load the pages from e.g. a high-speed serial connection to another system, or an SD card or whatever). Each stream could have different information like you would switch channels on old Teletext TVs. And a teletext stream can have up to 800 directly accessible 40x23 character pages, and unlimited "rotating" pages (i.e. pages that refresh every few seconds to show different information without interaction). Unfortunately I live in a country where Teletext was never a thing, and I have a few other projects I'm working on, so this is one of those "if I ever get to it" things.
===Jac