I think if you want the fastest seek to line on the fly without massive memory overhead, you could go the XS approach. Write a C function somewhat like this -

seek_line(FILE *f, long lineno)
{
  char buffer[65536]; # 64k buffer
  fseek(f, 0, SEEK_SET);
  
  // read in 64 k of text at a time
  fread(buffer, 65536, 1, f);
  
  // then count number of \n's
  
  // if found the desired number of lines, then
  // record the position found, fseek to that
  // position in file, and then return

  // if not enough lines, read next block of 64k text
  // and repeat until you have the desired number of
  // lines. fseek to the absolute position in file
  // for the desired line, and then return
}
[download]

Expose this function in Perl, so that you can do

seek_line($fh, $line_no);
# and then read as normal
[download]