You are right in that external AREF voltages lower than 1V are not going to work -- see Table 29-16 of the ATmega328P datasheet which specifies this very thing (AREF must be in the range 1V to AVcc).
You can indeed amplify the signal (which will amplify the noise too, and add a little bit extra to boot), or look for an external A/D converter with an extremely small AREF input and also very high input impedance. Not only would an amplifier boost the voltage it also isolates the microphone from needing to supply any current (which it probably can't do). My guess is you won't be able to get away without using an amplifier, but that's not such a bad thing. You can get ultra-low-noise amplifiers (look at "instrumentation amplifiers" for example).
The QuadRAM shield
: add 512 kilobytes of external RAM to your Arduino Mega/Mega2560