Assuming each line has something unique in it, such as a timestamp, you should only need to read the file backwards from the end, and stop when you read a line you've read before. Each run records the last line it has read, rather than the tell position.

The hard part of this has already been done for you by modules such as File::ReadBackwards and File::Bidirectional.