I think, that reviewing some of the existing video controller designs quickly reveals, that small CPLDs like XC9700 or MAX7000 don't have the required amount of logic cells and registers. So you clearly have to go for a small FPGA. There are some including nonvolatile configuration memory, e.g. XILINX Spartan-3AN, Altera MAX II, more devices from Lattice and Actel. Configuration memory can be a single 8 pin IC connected to the FPGA, in so far, it shouldn't be a problem to use "volatile" devices as well.
The clock input requirement isn't specific to FPGA, I guess, you'll remember it from legacy video controllers.
The graphic controller designs I know are basic, memory mapped controllers, you'll find them with development kit reference designs from FPGA vendors or opencores.org. Performing complex "graphic commands" is another thing. Even simple drawing commands can already require a considerable amount of logic cells.