Contrary to some of the statements here, while there are some quirky SPI PROMs out there, there are also some standard instructions used by a large variety of SPI PROMs, including the one you've chosen.
As vicatcu already mentioned, there are good 'bit-bash' cables available that can directly program SPI. Signal-wise, SPI looks a lot like JTAG, so any bit-bash type of cable should be able to be used provide the interface is open source. The internal protocol of the flash is fairly simple.
We use the big brother of the part you're looking at to boot our FPGA boards (256M - 2G). The addressing has an extra byte to handle the storage volume, but otherwise the commands are basically identical.
The type of PROM you're using has to be erased by sector, then programmed by page. Reading is significantly faster than writing (in the case of the ones we use, programming can take half an hour, but reading the whole PROM takes under a second at 108MHz).
Now for the commands: There are way more commands available in these devices than are actually required to program them. You actually only need the following:
- RDID (read ID) - just to verify the PROM and signalling before you do anything more complex.
- WREN (write enable) - needed before every write.
- PP (0x02 - page program) - needed to program a page.
- SE (0x20 - sector erase) - returns bits in sector to '1'.
- RDSR (0x05 - read status register) - needed to monitor erase / write cycle.
- FREAD (0x0B - fast read) - read PROM data and verify write.
If you want more information look at answer notes on SPI programming for Xilinx FPGAs on their website (http://www.xilinx.com). They implement a reduced subset of commands so their FPGAs can boot from these devices.
I designed my own programmer to do this based on what I have available and wrote a programmer script in Python, but you can do the same using a cable. In your case, I would seriously consider doing everything indirectly through the MCU as Michael Karas suggests. You don't need to program the whole PROM from the MCU in one go - you can do it by sector.