IMO gearing is not your problem, if you do the math your cruise RPM in top gear will only change by a few hundred RPM if you swap to 3.23's which makes almost no difference in fuel consumption by itself. If you didn't have overdrive or were running shorter gears like 4.56's I would say 'MAYBE' but in this case I really doubt that will fix it; you'll just lose acceleration. Like Blue87D100 said, people have gotten better gas mileage from carb'd old-school engines without overdrive and similar rear gears.
I would first do like others have suggested and make absolutely sure the computer is doing the right thing. Get a wide-band O2 sensor and check the actual Air/Fuel ratio; even if the computer isn't throwing any codes it could still be running way rich. The fact that your O2 sensor was sooty when you pulled it should be enough evidence of that. Driving around with a pig-rich A/F ratio just washes oil from the cylinders wearing out your rings, and dilutes the oil making it less viscous and less able to lubricate highly stressed components. Not to mention it pollutes more, for no good reason...
