Maybe I'm not understanding your requirement, but it seems to me you could just read in one window's worth of sequences, shuffle them, and write them to the file. Then you could empty the window buffer and repeat until you reach EOF. This way, your memory will never grow larger than the window size.

The algorithm is a little trickier that way because you need to deal with sequences that overflow the window, but I don't think it should be too hard.

EDIT: After reading hdb's comment, I would also suggest you go that route. That seems even better than what I was describing.