Work it just like eating an elephant: one bite at a time. That job will take a while, but with patience it can be done. Sometimes the best way to route wires is not the most direct route, so figure in some extra romex. I did a 2 story with a basement, and the only way to run the 3 conductor for the stairwell was down from the switch to an ac chase, up into the attic, then back down into the upstairs switch, almost 100 extra feet of wire to avoid a massive amount of demo in the center of the house. Point is it can be done, take your time and look at all your routing options before settling on a path.
