[Bigbuck]

If you want it to be all internal, which is possible just difficult to do, try to find an electrician or someone who took electrical wiring training. Most likely they have done wall fishes before. It really isn't that difficult it just takes a lot of time. We did it when I took the course and I've done it a few times working as a cable technician.
As for tools, definitely get a fish tape and/or fish sticks. I would also recommend a flexible drill bit for drilling through the floor joists/studs. I bought the Klein punchdown and crimper for work. Haven't had any problems with the crimper but the 66 blade that came with the punchdown breaks fairly easily. Damn replacements aren't cheap either. Use cut in boxes as it makes things look a lot better and you can coil some extra cable in the box just in case.
You can look online for the standard so you get your pairs correct. It doesn't matter as long as you keep them all the same, but it's best to use the industry standard.
We run all of our coax outside and I can't tell you how many outlets I've replaced because of squirrels. Running it outside should be a last resort. Just looked and I'm about 2.5hrs from you haha.