For parts that are just logic, I write them on a real computer and create test harnesses and test them in a UNIX environment with a debugger, if necessary. When they are working as expected, I paste them into a sketch or module.
This is only possible for something like a communication protocol or something, that has very fixed interfaces. If you have interrupts or special hardware to debug, you have to do it on Arduino hardware.
I have found some things help there: Using a MEGA gives you extra HW UARTS, which may make it easier to generate debugging information. It also has more memory, so having gobs of extra debugging crap around -- buffers to format debug messages and strings and whatnot is much more feasible.