Really is sounding more and more like a bad connection point somewhere near the batteries / starter. The reason I say this is because the lighting system is not attached directly to the ignition / starting system. This is exactly what happens when you leave your lights on all night and your battery barely has a charge in the morning... I'm not saying that is what happened, but it is the same symptoms. That's why I am leaning towards current carrying problems. This would also cause your lack of voltage at the starter relay.
Do you have different batteries you could try to use just to test it out? Either that or find somebody with access to a VAT tester and have them do a load test on the starting system. Or one of those fancy Fluke testers that send low voltage AC current through the battery to check its condition. Those work really well. Like I mentioned before, you may have a loose, corroded, or damaged terminal on your batteries. If you are testing the battery with a VAT, that will really tell you if you have current carrying problems at the terminals. Putting a multi-meter on the batteries will tell you voltage, but tells you nothing about if your battery can carry proper current (amperage) through the posts. Multi Meters need very little current to obtain a reading, but your starting system needs hundreds of amps to operate. If the batteries check out, then I would look at the physical connections.
Use a battery terminal cleaner brush on all the posts and cable clamps first. Also check for corrosion in the crimp connector where the wire from the battery cable meets the terminal clamp. If you see green or white powder in there, it is very possibly your problem and I would check the resistance of that cable with an Ohm meter. (You can clean that off with baking soda and water mixed into a paste) That goes for both ends of the cables. Everything should be clean and tight. Even minor corrosion at the ends of the cable can actually be up to a foot down into the wire insulation. If that is the case, you would be best off replacing the cable in question. I also recommend in any case, to use some dielectric grease on all the connections to keep corrosion at bay.
With the ignition off on your truck, you should have at least 24 volts at the B+ terminal of the starter solenoid. Probably be closer to 25.5 volts with fully charged batteries. Check this connection for voltage first without anything on and then try it again with the headlights on. See how much voltage you dropped. It should be only a couple volts. If it is a lot, then you do have a bad connection between the batteries and starter. If you have no major drop off, you have issues further up the system...
I can't remember what manual number off the top of my head, but the maintenance manual for your truck is on this site under the "Resources" tab at the top of the screen. In there you can find some very basic wiring diagrams and troubleshooting tips. I have not had a lot of luck using the diagrams in the manual because my truck's wiring is far off from what they claim it is supposed to be like, but that is military maintenance for you...
Once again, I wish you luck!
