I add another option:
4) use VGA 640*480 with 16 colors or 320*480 with 256 colors, you use more or less the same bandwidth as PAL 640*256 with 256 colors (I know it's not nice to be so limited in resolution or color, but this really requires no extra hardware! :-)
