Thanks to Aristotle for the seek correction!

New suggestion: Okay, read by character, building array of positions of '\n's. Shuffle that, then read between the '\n's. into new file.