If there is visiable contamination in the system, I would replace the lines, or at least blow them out, to make sure they are clean. Also there can be external problems with the lines, like rust due to mud/debris packed around the lines along the frame rails. Track the lines, and make sure they are all right.
While I was doing the job, I would also look at the front end ball joints. There are some bronze axle bearings and seals on the inside/differential side that can wear and leak. Its a long way into them, and that would be the time to check them. Also the trunion bearings and the felt seals for the ball joints. " Vintage Power Wagon", has all that stuff. There are no doubt other Venders too.
My lining has never been replaced. I re-used the shoes. They (M37) are not famous for stopping real fast in the first place, especially loaded, with a trailer. Maybe a softer lining would work better. You might check with a brake shop, but you will need to have somebody that knows what they are talking about, otherwise, I would just re-use the old shoes/lining, if they are not contaminated with lube or brake fluid.
Also, check the clutch/brake pivot pin & its bushings while you have that master cylinder out. That mud/splash shield on the rear of the left fender comes out, to give you more room there.
Good Luck
Lee in Alaska