I don't think there is going to be an answer to this. Adding headlights is a significant modification, involving changes to the vehicle wiring. No rental company is going to allow it.
Possible solutions might be renting a higher end vehicle with better lights, buying higher powered bulbs for headlights and replacing the rented ones (unlikely to be practical in these days of sealed units), and having a friend shine a high powered spotlight out of the front of the car (possibly illegal and possibly dangerous). I'm not recommending any of these except the first.
I would reiterate that if you cannot see debris or animals in the road ahead you are driving too fast - even if you are doing 20kph. I drove round Newfoundland for a few weeks without ever encountering this problem. I frequently drove the speed limit at night on major roads and 50-60kph on back roads, but I also drove on roads where 30kph was the safe limit at night. That's the way it is.
If you are unable to see significant debris in full beams on a wide straight road at 40kph you might consider getting your vision tested. There are conditions which affect night vision before daytime vision.
(It should be said that the problem is not with the rental companies but the manufacturers, and possibly road traffic rules. I do not know enough about Newfoundland regulations to repeat what was said in comments by Nate Eldridge, but I find it easy to believe.)