I towed a 22' TT that weighed 4800 lbs. at the scale with my 2003 Chevrolet Silverado extended cab 2WD LS 5.3 liter with 3.42 gears just fine in 3rd gear. I averaged just over 10 mpg towing and could get over 20 mpg on the freeway when not towing.
That same truck (or up through '06 for the price point) would be great. A 4WD will likely have 3.73 gears and tow even a little easier.
If you don't need a full crew cab, the extended cabs will get you more bang for your buck (higher payload, better fuel economy, and a lower price at the same mileage and options).