I don't think I would give up on those 600 LED's quite yet. I don't think this is an impossible task by any stretch. First let me give the caveat that I'm not any good at AVR assembly so I might be off base here.
The english data sheet varies from the chinese one google finds for the values of T1H and T1L (1.2u/1.3u versus 2.0u/0.5u). In either case it's a total of 2.5u for each bit. This works out to exactly 40 clock cycles (2500ns / 62.5ns) on the Arduino. The +/-150ns tolerance means that you can be over two clock cycles early or late for each transition. I don't think you can expect to write the loop in C++ and have the timing work out. But I think if somebody was reasonably proficient at assembly they could write a loop to manage this. The actual work to be done per bit is just two OUT instructions at 1 cycle each. That leaves 38 cycles for managing the loop itself. That should be plenty. You could unroll the inner loop over individual bits and inline that if you wanted. That gives you something on the order of 304 clock cycles to manage your loop over the bytes of data you want to output. That's tons of time. You can use SBRC/SBRS instructions to control the falling clock timing. Those instructions are nice because the timing is identical whether the condition matches or not.
The 2801's are very easy to work with though. I've got 350 of them up on my house right now as christmas lights. Let me know if you have any problems controlling them. I've got a hacked up version of shiftOut which is significantly faster than the stock one. You could also try the FastSPI library if you want to use SPI to drive them. The last batch I bought didn't work with FastSPI though and I didn't take the time to figure out why. I'm driving mine as four separate strands, so a single SPI line wasn't going to work for me anyway.