Для этого вам понадобятся либо строки фиксированной длины (подробности реализации должны быть очевидны в этом случае), либо информация о том, сколько существует строк и (необязательно, для лучшей производительности) с какими смещениями внутри файла они начинаются (индекс сортов).
Для небольших файлов вы можете создать такой индекс по требованию, когда вам нужна случайная строка.Чтобы сделать это эффективно для больших файлов, вам нужно постоянно сохранять индекс, возможно, в отдельном файле.
Если строки имеют примерно одинаковую длину и вам не нужна идеальная «случайность», вытакже может выбрать случайное смещение байта внутри файла и отсканировать ближайший разрыв строки.