With 35" tires, your truck isn't going to get good fuel economy, no matter what you do. 35's are pretty big for a 10 bolt equipped truck anyhow. If you're just driving on the street, not a big deal. Going off road, I see snapped axle shafts in your future.
If you stick with your stock setup, 3.73 or 4.10 would be a good gear setup for 35"s.
If you go to a 700R4, I would seriously think about 4.56 gears. I think 4.10 would put alot of unneeded strain on the 700R4 when cruising down the highway at 60
Here's a gear calculator to play with
http://www.ringpinion.com/Calculators/Calc_RPM.aspx
If you're going with lower gears, why not just swap to axles from a 3/4 ton or 1 ton truck? Most of them are already in the 3.73-4.56 range and it would solve any strength issues.