a fast external converter would be possible - not easy but possible
even if you got the data at full speed can you work with it (see below)
you can skip the early parts of the data - either by tossing it out (sampling & over writing) or delay first sampiling till the ~first valid bits are available
do you have to run at MAX speed?
other things ( at full speed ) to worry about
MEGA runs at 16 Mhz (62.5ns) this means if you had to run the sensor at full speed (5Mhz / 200ns) you MIGHT beable to fit 3 risc instructions in the time between samples - i haven't looked at the chips instructions but even if you wrote a super tight loop in asm(NOT C/C++) i'm guessing you would need 5-10 cycles (to read /save data / test if done ) no irqs, no timers
(the above is why i'm using a Due)
and a problem that i'm fussing about - do you know (i don't) when is the exposure time for the chip ? it likely needs 1-100ms to collect data (enough photons to make a image) - do these chips double buffer the data (so you have the 1-100ms to pull the data) or can you only run one line at a time ...
aaaghhh...