To reduce RAM usage, you store the strings in flash; that will give the big reduction in RAM usage; with that you can use the xxx_P functions.
You can also store the array of pointers in flash; that will give a little bit extra reduction (2 bytes per pointer).