My parts were a pretty successful 35" setup. Standard travel Icon's no sway bars, Camburg uniball UCA (Similar enough to the Icon), 1.5" body lift. Removed mud flaps, BMC, SCS wheels w/ -10mm offset. slight trimming/beating of the front pinch weld/firewall and fenders. The amount of suspension lift you have has no effect on the rubbing so don't worry about that. I could tuck the rear 35" tires way up into the wheel wells, stock bump stops. The body lift helped with that.
The lower link is important for dragging over rocks, I only slightly bent 1 stock lower link in all my wheeling so far, but if you were to adjust the wheelbase I would want the upper links too, to adjust the pinion/driveshaft angle.
As for the solid bushing do you have a game plan to fix a broken diff on the trail or trailer it home? Factory ATRAC and my 35" tire setup worked well enough for me, kept me happy for a couple of years, but I was happy to have the solid bushing in there after I had my gear failure. If you wheel alone fixing it is not an option in which case I would run 33's or get a spacer in there.
For gearing its all personal preference as I've heard some guys say its mandatory but I got by just fine with stock gears, 35's, and the 05'+ V8. Just don't expect to use cruise control unless its flat or downhill. Passing will require a downshift at interstate speeds. If I had a dollar for every FJ guy I knew that has stock gears on 35's... I'd have a couple more bucks; and they have terrible aerodynamics + the V6.
I'd carry a cheap CV, a tie rod, a stock/cheap lower rear link if your's are stock. Any tools you can think of too.
With 35's and armor the V8 makes more sense to me.