If you can find an eight bit VGA card it shouldn't be impossible but there are some things to consider.
The only 8 bit VGA cards I've got are 512k cards. This limits you to 640 x 480 in 64k colours or 800 x 600 in 256 colours which isn't too bad but the access time is slow. Even for 640 x 480 x 256 it will take a 2MHz 6502 over a second to write to every displayed pixel, and that's assuming fast 6502 code. The lower resolutions would be better, 320 x 240 in however many colours or even text modes shlould be at least reasonable.
The other downside of VGA is you will need the datasheet for the VGA chip on the card to anything more than the basic resolutions and possibly even to get the card to do anything at all as you won't be able to use the on board x86 BIOS.
An easier bet would be to use any of the general purpose on screen graphics chips from teletext to the menu chips used in sat boxes and video recorders. These often have a two or three wire interface, on board memory and can do straight graphics or genlock (overlay) on a video source.
I prefer the teletext chips as they often come on sub boards so you get a complete working board and don't have to mess with building the video section. You can see an example at ..http://www.geocities.com/leeedavison/i2c/index.html
The only extra parts, apart from the i2c interface, on the board are a power socket (for the +12v), a video in socket (for genlocking) and an RGB out socket.