My reaction to this kind of post is to consider bike touring because although I have enjoyed hiking and backpacking for many years, walking along a road is just plain boring and insufferable.

I think a trip of this scope is nicely suited to bike touring, and bike touring is quite compatible with backpacking - much of the gear is identical. When you arrive at a backpacking venue, simply stash the bike securely and head for the woods. I usually hike in low cut shoes, the very same ones in which I backpack.

Your daily travel on a fully loaded touring bike is easily 70 miles or so. When in shape, daily averages of 100 miles are quite achievable. This is a much better way to deal with some of the waterless stretches you will encounter.

Traveling by bike really puts you in contact with the country you are traversing - quite different than traveling by car.