I would go through the file once in order to create an auxiliary data structure holding the byte offsets to the individual lines. As that data structure will probably still be too large to fit in memory (depending on the average line length), you'll want to store that in a file — but this time with fixed record size, so you don't have the same problem as with the original file...

You can then access a random line like this: multiply the line number with the record size, seek to that position in the auxiliary file, read the byte offset found there, and finally seek to that position in the original file.