All~
Actually you can make this work. You use the same technique as a split-and-merge sort. After you have randomized each subgroup, you collect them together into one big random group by randomly selecting which group to take the first line from until they are empty.
This might even be a good way to do something like this as split and merge is the technique employed by databases to sort things that wont fit in memory.
First break the file into memory sized chunks and use the Fisher-Yates Shuffle to randomize them. Then take the randomized runs and shuffle them together by randomly selecting which one to take from next. Repeat the process until you have one one very large random run. I know it will provide an even distribution if you combine all of the random runs simultaneously, I have yet to convince myself whether or not it will still provide even distributions if your shuffle only takes two random runs.
UPDATE: I have convinced myself that you can do it by repeatedly shuffling together two runs, as long as you select the runs to shuffle together randomly every time.