Optimizing Arduino File Selection from SD card
You have several possibilities:


Do not store the names of all files, but use the index and iterate through all files again. Disadvantage: this takes a lot of time (every time you need the file name)
Add SRAM to the Arduino (e.g. 23LC1024, 23K256), depending on your memory needs. Disadvantage: you have to 'manage' this memory yourself.
If you know something about the file names, you might generate the name. Probably it's not the case, but just to add another option. E.g. if you know that file nr 10 will always be called 'File10.txt', you can 'generate' the name.
I don't know exactly how you want to use the file names, but you might store only the latest x files used, to prevent having to iterate again reading the SD card. Of course, this only helps if there is a high chance the last x files are used more than the non recent files.


Update:
If you need to read the files while leaving the Arduino unblocked, you have to incorporate it in your loop, but don't read all the files in a loop. Something in pseudo code like:

bool readingSd = false; // True between reading first and last file
uint16_t lastTimeRead = 0; // Last time read

void loop()
{
   // Check if file read needed (initial or one hour past, I don't take
   // overflow into account
   if (lastTimeRead == 0 || (lastTimeRead + 1000 * 60 &lt; millis()) 
   {
      checkReadFile();
   }

   // Perform your normal code... this will run between processing/reading
   // one file/dir.
   ...     
}

void ProcessSingleFile()
{
   readingSd = true; // Within reading first/last file
   "read/process ONE file or dir (without containing files)";
   if ("last file read")
   {
       readingSd = false;
       lastTimeRead = millis(); // Move to top to prevent reading time
         // between first/last to take into account
   }
}