I've been up against that problem with my '62 one ton. My wheels were 17.5's tubeless. I really didn't mind that size until I priced a pair of tires for the front

. For less than the cost of two 17.5 tires,I bought two new 16" wheels and two LT235/85R-16 tires. I'd planned to replace all of 'em with 16's;thats when I discovered the clearance problem. As I see it,there's two options from here;one is to find some 19.5's which appear to be common on bread vans and such,and will give you considerably better gearing than stock,or,as you mentioned,upgrading to a later rear end,with better brake design and a good choice of gear ratio. Generally speaking,I think the rear end change would be my choice,as I still have plenty of tread left on my rear skins;depending on whether you buy new or wrecking yard tires and wheels,it could be cheaper or around the same price to go either way. If you plan to replace your wheels anyway,I got my 16's from Les Schwab. then,you can generally pick up a duallie rear end from the wrecking yards for around $150.00;that'd fix you up pretty decent. Look for a 3.73 ratio if you can. That'd be about the best ratio for your truck,and it would be good to watch for one with positraction. I think those are often found in 4X4's.
BTW-if you happen to find a great deal on duallie rear ends,pick one up for me too-I need to change mine too,but Elko's pretty dry for stuff like that.
Speed