If you're okay with grayscale, you don't need 1 MB buffer space. With the YUV422 colour space, you can extract only the Y component and need only 640*480 = 307kB buffer for a VGA grayscale image.
However, according to this, you can set the hardware serial baud rate to 1M-baud and transmit the image bytes as you receive them without buffering. main() shows how to set up the serial port and you can also see how they received each VGA pixel byte in Bayer-RGB and transmitted immediately; notice that all interrupts are disabled first, given the high-speed nature of the transfer. But instead of Bayer, I'd recommend you use YUV422 instead, meaning the camera sends 2 bytes per pixel. Because you're only interested in the Y byte, you can place that in the UART buffer and use the time spent in receiving (and discarding) the second U/V byte to give the UART peripheral some additional breathing room to send the Y byte, before you send the next one.
Regarding the high baud rate, the crystal frequency of the Arduino doesn't matter so much because you'll only be transmitting to your PC, which should be able to handle the speed even given the rate error. Note that in main(), double speed async is enabled, and UBRR is set to 500 kBaud to obtain 1-Mbaud. Also notice that an 8MHz PWM signal was used to clock the camera (XCLK signal) with no PLLs activated in the camera register settings. This is another tutorial related to the same code; may clear up a few things.
If you really want to use a chip solution, you can look up parallel SRAM like the HM628128; it's only 128kB though, you'll need to find a bigger one to hold an entire frame of 307kB. Parallel SRAM are great because you can attain really high write speeds because of the simple interface. You'll need some sort of counter connected to the SRAM address lines clocked by the PCLK line (divided by 2, since you only want every other byte) so that every pulse increments the address. This same clock will feed the nW signal to actually clock the data into the SRAM (after satisfying address setup times somehow). The camera data lines will be connected directly to the SRAM and you activate the SRAM's chip select signal based on your monitoring of the camera's VSYNC signal (to know when a new frame's about to start). When the frame's done, you read from the RAM and forward the bytes to your destination.
All this assumes you aren't trying for video, merely taking frames "once in a while". Though the first solution will work for video, albeit poor video.
