This post has tickled my fancy. Makes me think of the kinds of projects we did back when I was a 3rd-year undergrad at MIT in the 6.111 class (digital circuits lab).
What if you were to use an asynchronous SRAM as a sort of frame-buffer and bit-map the sync, R, G, and B values across the 8 bit word? For instance, bit0=vsync, bit1=hsync, bit[2:3]=R, bit[4:5]=G, bit[6:7]=B. The sync pulses can be wired straight to the appropriate pins of a 15-pin VGA connector, and the R, G, and B D/A could probably be done with just resistive suming. Maybe with an NPN transistor as the line driver.
The amount of memory you would need would be 640 x 480 x (an uplift factor to account for vertical and horizontal refresh times; I don't remember the exact values, so I'll use a 10% uplift for now) = 640 x 480 x 1.1 = ~338kBytes.
As for timing, VGA is 640 x 480 x 60Hz x (again, I'll use the 1.1 uplift as before) = ~20Mhz.
So you clock the memory continuously @ 20Mhz. Also, tie the read/write pin to the oscillator so that you're reading every half-cycle. Come to think of it, you'd also need an address counter also clocked at that frequency. That could simply be 1 or 2 dedicated TTL counter chips.
Now you have the makings of a stand-alone frame-buffer than can generate a VGA signal with up to 4x4x4=64 colors.
What's left is figuring out how to build a write-only interface from the PICAXE to the SRAM. You should be able to source the necessary number of address and data pins from the PICAXE, and use some outboard 2:1 multiplexors (using the phase of the clock on the select pin) to select between the write address/data and the read address/data.
In this way, the speed of the PICAXE is almost irrelevant to the VGA timing, but does rely heavily on outboard logic.
At power up, since the memory is volatile, you'd have to wipe the memory clean and then write the appropriate 1s into the vsync and hsync bits at the appropriate address locations to establish the proper sync timing to the display. Thereafter, you can start writing RGB image data to the other address locations.
The cool thing, though, would be that you could literally watch the image taking shape as the PICAXE does it's calculations and writes into the frame buffer.
This is all off the top of my head at the moment. Although, I actually did something a lot like this years ago using an EPROM to display a static image on a monitor (so rather than writing the memory with a PICAXE dynamically, I wrote a program on a PC to convert the contents of a BMP file into an appropriate HEX file that I burned into the EPROM).
EDIT: Actually, you can't wire the vsync and hsync directly out of the RAM to the VGA connector. The output of the RAM will be 5V and VGA needs a 1V p-p swing, so you'd need, at the least, a 5:1 resistive divider on those 2 signals.
