If it’s stored on board, it isn’t telemetry.
The Microchip sensors you mention (24LC256) have byte-writable modes as well as page write. Unfortunately the predefined buffers in the Arduino I2C library aren’t big enough to support its page-write operations. FYI, the 24LC1025 is 4 times as large (but must be addressed in such a way that it looks like 2 different devices on the I2C bus). You can use several of these chips; I recently flew 2 on a balloon experiment, and the addressing is such that you can easily connect 8 of the 512kbit-or-less variety or 4 of the 1024kbit devices to the same bus.
My concern for I2C devices is that the speed is slow - you may miss data.
I’m currently looking at the Atmel AT45DB161D “dataflash” chip. It has an SPI interface, which is a few orders of magnitude faster than I2C. It also has two onboard RAM buffers, so that you can fill one buffer, issue a write command, and start filling the other buffer while waiting on the write to complete. There is code for this family of devices on the playground.
An SD card has an SPI mode, so you can use it as a big SPI flash device. I’m not sure about write speeds, etc, but the size and availability are right. If you do write directly to an SD card, there is no FAT filesystem, so you can’t just pop it into a computer and double click on a file. You can read raw data off (e.g. using dd on a unix box).