Question about configuration EEPROM or Flash
Somehow let end users use the computer application to store the setup file they created into the Arduino's extended EEPROM (I will add a 64KB EEPROM for this). However I don't know if a computer application can be made that can do this (i.e. store the information to EEPROM).


Perfectly viable - although an SPI Flash chip would be more appropriate.


  Do like above, but store it in Flash (as far as I know, only the Arduino computer application can do this, to send a sketch to USB).


It is the bootloader that can write to flash. I don't thing the main program can write to flash, or it would wipe itself out. You may need a special bootloader with your own protocol and upload program to go with it.


  Create an application that 'adds' the setup file to the sketch. However, probably end users cannot store it in the Arduino without the Arduino software which is unwanted.


Perfectly viable, but tricky to say the least.


  Use a SD card and read information from there; however, I read 512 bytes SRAM is needed.


Yes, 512 bytes of SRAM, since that is the size of one block on an SD card. But an UNO has 2048 bytes of SRAM - more than enough for SD card support.

The SD card would be my route of choice. It's the easiest from a user's perspective (slip the card into their computer and copy the files), and pretty simple and straight forward to connect and program the Arduino for.


  To make it more complicated, I want the Arduino sketch to handle like reading on average 50 random bytes from the storage the setup file is stored, and perform several algorithm (not so difficult but still) and do this in max. 10-20 ms.


If you know where in the file the byte are then you can seek() straight to them. Takes almost no time. 20ms is an eternity for a microcontroller.