So I wonder, what's faster/easier/... SD cards, USB Pen Drive or even an extra EEPROM chip?[/edit]
Forget about USB drive... it would be pretty difficult to interface it with Arduino. In terms of speed, according to my experience, an I2C EEPROM probably is going to be the fastest and very little code is needed.
I know I can store data in the flash-memory, but from what I could see, its read-only, right?
No Flash memory can be written and re-written.
Imagine 400,000 midi events, thats going to take much more memory.
Hopefully, you are not going to load all data at once.