These are 256 K bit not byte. Your speed requirement is about 100 times faster than the SPI bus.
The arduino processor is about as good as computer processors were in the 80s. How many VGA computers were there then? None this was in the days before VGA. Graphics capabilities were limited. While a circuit read out bits from a memory to generate the video, that memory was not written to at video speeds but at slower speeds. The CPU architecture of these computers meant that external memory could be part of the computers main memory map. The architecture on processors like the arduino separates out data from memory, they occupy different spaces and they are not designed for extending the memory.Sure you can bit bang external memory but it will never be at the speeds you are talking about.Simply you have the wrong processor for your project so change the project or the processor.
How many VGA computers were there then?