Mmm. Best thing to do is run through your file once getting all line locations and writing them to a new fixed-length file. Then you can randomize on that file and easily pop your line out of the original file whenever needed. I'm assuming that with millions of lines to randomly pick from, nobody is going to notice that your line pool is only updated every x number of days.

Or you could convert the entire original file to a fixed-length file, but this requires that the lines be more or less the same length, or you're going to end up using huge amounts of disk space.