Well, a sentence as short as that one presents no possible misunderstanding as to sequence of events, so you don't have to backshift. So number 3.
"I had to move all the furniture before the guys came to shampoo the carpet," Mary said.
Mary said she had to move all the furniture before the guys came to shampoo the carpet.
Here, neither had to nor came is backshifted because there is no confusion over sequence of events.
Another reason is that had to is functioning as a modal verb expressing obligation. It is already the reported speech form of both have to and must (obligation). Further backshifting of had to would be rare, just like there is no further backshifting of could, which is already the backshifted form of can.
For general reference see Reported speech: indirect speech
from English Grammar Today (Cambridge online)