How about splitting the file down into to a number of smaller files each with a set number of lines on it. So you could end up with 1000 files of 500 lines (for example). Then you just need a mechanism for breaking a line number (in the 500GB file) into a filename and line number within that file, quicker access all round.
The best way to eat an elephant is one bit at a time...