We've published a library to attach FRAM (ferroelectric RAM) to the Arduino. Details here: http://hackscribble.github.io/hackscribble-ferro-library/
We wrote it for a project with similar requirement to yours: caching test data before sending it on to a controlling PC. The library includes functions to create arrays of types of your choice, and to read / write them with random access (as per normal arrays).
First version of the library (not tuned for performance) takes about 45 microseconds per write and 30 microseconds per read. So writing up to about 22,000 samples per second.
We are actively supporting the library and would like to see it used in applications. So feel free to contact me if you would like more information.
Regards
Ray