It's your truck man, and it's up to you. I'm not gonna knock your decision for Big Tires.
A 7" Suspension Lift would be a better way to go, because while the 3" Body Lift is legal and safe to an extent it's not something i would trust.
I can feel the floors flex (when the truck is at an extreme angle) in my dad's '75 D300 Dumptruck with stock height bushings, a 3" Body Lift is going to amplify that and lead to stressed mounts and cracked panels. There are alternatives, but they require alot of work (custom body mounts on the Frame & Cab, aswell as a redesigned structure/support under the floor).
With 7" of Suspension Lift you don't have to worry about the issues that come with a body lift, and it should clear the 40's for a Street Rig. I can technically fit the 40's off of my diesel under my '76 Ramcharger with stock suspension. The 40's don't have alot of room with the stock suspension though, infact i would be afraid to sit in the RC or turn the wheels
4" wouldn't be enough because the tires would eat the fenders when you turn the wheel or pull over a curb/bump (like into a parking lot or gas station) 7" would get you close, just don't take it off roading or it will make it's own clearence/space for the tires to fit.
That being said, Fender Trimming/Cutting can be done and look stock/awesome (check out the build thread for BradicusX's Ramcharger). I knocked nearly 3" out of the Front & Rear of the Fenders on my Diesel and tapered the cuts (with excess to create a new lip on the inside of the fender) so that when it's done it looks stock, only with more room.