lThere are some interesting comments in the previous posts ... "troubles of a diesel"? and the comments on payload? I would first ask a few questions. What size truck fits your needs best? What are your specific needs besides pulling a 4k lb. trailer?
A few things to remember:
1. "Pulling power" is a result of transmission gearing, not engine horsepower. Perfect example, my 87 hp 2.5 ltr engine (1972 Pinzgauer military troop transport) will pull 5300 lbs. It has lots of gears. (10 forward, 2 reverse) GEARS are the answer. If you want to keep the same truck, you might look into either swapping gears, or swapping transmission. That's just one solution. If you want to learn about that one, contact a local 4x4 transmission expert. Be forewarned, some transmission people are unable to calculate what you would need (they are accustomed to just fixing existing systems) so you need to speak to someone at a custom performance shop. You might spend $2k to $3k doing this.
2. As previously mentioned, you can soup up the engine, but then you still have the gearing problem. A more powerful engine won't get you better pulling power, just less gas mileage and a louder engine.
3. IF you decide to look for another vehicle, keep in mind that tow ratings are maximum ratings. So, if a truck is rated at 5000 lb tow rating, pulling 4000 lbs. is using it at 80% of the max rating. It will be difficult. If you buy a truck with a 12000 lb rating, you will be pulling at 30% of the rating and you should enjoy the ease of towing much more.
4. My personal preference, along with the majority of people in the developed world, is Ford trucks. A newer Ford F150 has enough to easily pull what you need. (Chevy is great too ... as are others, but my personal preference for work trucks is a Ford)
I hope this helps.
Bumber