Whichever way you decide to go, put in plenty of money. Re-wiring can be very time consuming and frustrating.
I think Trumpy has you on the right track. It is almost as much work to install an equipment ground as it is to install a new cable. If you go for installing equipment grounds, keep in mind at some point you may need to use #6 copper, see 250.120 (C)
When I was doing house re-wires, for a 2 story house, I usually took the new circuits up to the attic and dropped down to each receptacle. Perhaps you can determine how the house was wired and use the existing cables to pull in new cables.
To sum up, throw plenty of money into your quote. You could easily end up working for minimum wage or less. Rewiring is a good way to burn up man hours.
Since Trumpy is a Red Green fan, always keep your stick on the ice.
