Another option, one that I've been pursuing, is using a TinyFPGA BX. It's got 16K of dual-port RAM built-in which is enough for text mode and some simple graphics modes; my implementation can do 80x25 VGA (16-color plus blink) and 160x120 in 6-bit color. It can already output video if I preload the internal VRAM, and hopefully soon I will have the bus interface sorted out so that the rest of my SBC can talk to it. I'll be putting all the design stuff out on github once I feel like it's ready for the world.