Store data in flash/EEPROM and process it in parallel
A common method of overlapping data input with data processing uses double (or multiple) buffering.  For example, one of two buffers is processed in the foreground (that is, in the loop() routine) while another buffer is filled in background (via interrupt handlers).  Each time a buffer fills, the usage of the two buffers swaps: that which was being processed now refills, while the recently-filled buffer gets processed.  To make this work, buffer processing must take less time than buffer filling.  

For recording conversion times, because free-running ADC conversions each take the same amount of time, you can just save fill-start and fill-end times with each buffer, and interpolate to find out reading times.

If you plan to process audio data at near-normal speeds, it's likely most Arduinos won't be fast enough to keep up.  However, using an Arduino Due probably is feasible.  The Due is based on an ARM Cortex M3 processor with 72 MHz operating frequency, 32-bit arithmetic, large RAM (for an Arduino), etc.

An alternative method of processing audio data is to use a frequency analysis chip.   Here is a low-end example:  The MSGEQ7 Graphic Equalizer Display Filter is about $5 in an 8-pin DIP package from sparkfun.com.  Apparently, it continuously measures peak spectral intensity in each of seven frequency bands, and can read the peaks out perhaps a thousand times per second.  Audio goes in on the "Audio in" pin.  A Reset pin resets an output-multiplexor counter to zero.  Each time after you clock a strobe line, a band's reading is presented as an analog voltage on a "DC out" output line; the band's peak reading is decayed about 10%; and the multiplexor advances one band upward in frequency, rolling over from highest to lowest every seven strobes.