What you have there is a mess, but you already know that. This is the type of job that if you farm it out to an electrician you will pay a fortune b/c it is a very labor intensive job, but if you are willing to put in some sweat equity you could probably save yourself 75% over hiring someone. Also your house is relatively new so the current layout of outlets and lights should be close to current code.
1. If this house is a single floor and has a full attic there is really no need to tear down the sheetrock with the only exception being directly over the panel. You are going to be pulling 20+ runs back to the panel. Its not worth dealing with that strip of sheetrock so just cut it out to the studs.
2. Buy some quality tools - a good pair of strippers, linemens pliers, fish sticks (you probably won't even need fish tape), a good 18V or better cordless drill and a 1/2 and/or 3/4 inch diameter 12" or longer spiral drill bits. You will also need some short spade bit to work under the eves of the roof and other tight spots. You will also need a multimeter and a wire tracer/tone generator.
3. Wire the A/C and air handler first. Your are going to want it. Wire the fridge second. You'll need a cold one at the end of each day
4. Work room to room. How you deal with the insulation is up to you. Personally I'd pick a room to work on and rake the insulation off of the top plates for that room so I could inspect for cut wires and replace it when I was through. You will likely find that some rooms - like the bedroom, dining room, living room, etc. are each fed with a single run directly from the panel and that the wires between the outlets are still in the wall behind the sheetrock. Every time you locate a cut wire you will need to go back downstairs and cut/smash the outlet box or switch box out of the wall and buy an old work replacement box for it. Its nearly impossible to fish a wire into an existing box so don't even waste your time trying. Once you find a cut wire head down and smash the box out from below it. If there are two or more wires in it you will need to determine which wire has been cut at the top plate. You can connect the tone generator to one set of wires, then use the probe to see if that is the cut pair. If it is cut it as short as you can, stuff it back into the wall and replace it with the new run from the panel. This process works best if you have a helper or you will be doing a lot of climbing in an out of the attic. Replace the box with an old work box and move onto the next cut wire. You be repeating step 4 alot - multiple times per room.
5. You will also need to deal with all the lighting circuits that have been cut out. Make sure that you know where each switch connects to!
6. Your panel should be labeled. The labeling will give you some clues as to where each circuit used to run to so you will know where to look for the cut wire for the run from the panel. There is also likely many more cut wires between outlets and lights that looped up into the attic so be sure you trace out everything.
If this seems like a lot of work, thats because it is. If you do not want to do ALL the work hire an electrician. Do not try and do part of the work and then hire someone. Electricians do not want to be liable for your mistakes and will likely refuse to do the work if you have already started in on it so be sure this is something you want to do. The only exception to that would be the service entrance (meter, panel, and wiring in between). If that is damaged you could farm that out and I would recommend that.
-rick