If you don't need all the strings in their 'manipulated' form at the exact same time you could always manually copy from FLASH to RAM buffer and do the manipulation there. The buffer can be used for any number of string manipulations.
There is no way to add more RAM so whatever you connect to store strings you will have to copy the string into RAM to manipulate it and copy it back out to auxiliary memory for free up the RAM for the next manipulation. There is a type of SPI memory called FRAM that I have heard is both non-volatile and fast: http://www.kerrywong.com/2012/01/15/using-fram-as-nonvolatile-memory-with-arduino/
Thanks for the FRAM tip. I will consider it seriously. I am assuming that it is way better than file/string runtime manipulation via an SD card?
Also according to arduino documentation
-Flash memory (program space), is where the Arduino sketch is stored.
-SRAM (static random access memory) is where the sketch creates and manipulates variables when it runs.
-EEPROM is memory space that programmers can use to store long-term information.
According to FRAM-X Add-on
512 bytes of non-volatile, ultra-lower power memory via I2C, which directly replaces EEPROM and FLASH.
What are the impact. Will the sketch load normally?