I regards to the ring and pinion vs. engine upgrade discussion: I have tossed some cash at cams, headers, 3RZ swaps and other tweaks at these trucks over the years and my experience has been that no amount of power upgrades will take the place of proper gearing. Also I have had a hard time noticing the perceivable gains from power upgrades unless I am in the sweet spot in gearing, if that makes any sense.
I have never built anything as hot as Glen's engines though.
All this being said 31" tires are not that big. I will be curious to see how you like your engine and cam with the 31s and 4.10s. I would guess it will be pretty tolerable.
My personal favorite for 31s are the 4.37 gears found in 1st gens or the 4.30s from auto/22re IFS 4runners.