I only saw one thing in your post that was worth doing - 4.56 gearing.
Things you didn't mention:
Drive it like a grandma would
Take the lift off
Buy a Hyundai
that's exactly what i was going to say, the gears would help alot and i think an electric fan may be worth it. i dont think everything else is gonna give you that much better mpg
another thing you could try is making the truck as light as possible, remove all the crap in there that you absolutely dont need.
xtreme 4x4 is doing an experiment like this on a 4x4 dodge ram with 33's or 35's. so far they've lightened up the truck a tad and put in an electric fan. i think thinner tires and gears are next, but i dont remember. but it may give you more ideas.