I'd probably use a variation on this. Read the file once saving the offset of each line. Shuffle the array of offsets. Step through the array, seeking to each offset in turn, and print the line at that offset.
Using seek() will avoid all that rewinding and reading.
By the way, you can do almost exactly this but without worrying about the nitty gritty. Use Tie::File. Just tie the file to @tied_file, shuffle the numbers 0 .. $#tied_file and print out each line in the array in shuffled order.
"My two cents aren't worth a dime.";