Programming parallel flash chips

I would look at the data sheet as you may not be able to flip the lines fast enough.
What you have looks like it would work but it will be quite slow to drive it especially if you use digitalWrite(), you will probably have to go with direct port access.

How about using a MCP23016 for your data and address, this gives 16 I/O lines from the I2C bus. It is a lot less messy.

http://www.arduino.cc/playground/Learning/I2C

http://www.neufeld.newton.ks.us/electronics/?p=241