1. If your memory requirements are not so high, I suggest to use external FLASH device like AM29F080 - 1 MByte device. The advantage is that it has an uC compatible address/data bus, has a large storage capacity and is very small size, requires only 5V single voltage. The price is also very good and will go down in the near future (in next 2 quarters the price will be the same like 29F040 now). You can make an array of a few such devices and you get the storage capacity of a few Mega bytes on the PCB of a very small size comparing the HDD.

2. It is not possible to read or dump the code memory if device is locked and all 3 lock bits (or 2 in some devices) are set. It was possible in the past when using a trick of dynamic EA (external address input) switching.
But now, EA pin is latched after RESET, so any further toggling of EA makes no sense.