I thought that it might be that the servo was drawing too much power out of the 5-volt pin
Probably yes. 12 V is the maximum to put into the barrel connector. The voltage regulator has to get rid of 7 V. Multiply 7 V with the milliamps the servo draws. That's theoretically the effect that's heating the voltage regulator, I think. Try using some 7.5 - 9 V battery pack instead.
, so I put a wire going directly from the battery through resistors (to step it down to five volts), and into the 5-volt pin on the servo. In short, it still didn't work;
That's not how power sources are regulated. A single resistor in series between your 12 V and your servo drops the more volts, the more current your servo draws (so when the motor is working, more volts drop, but when motor stops, only the internal electronics work, which means they get almost 12 V). With two resistors you get a voltage divider, which can get you 5 V when no amps are drawn. But again, the voltage changes, when more amps are drawn.
To test if your servo is ok, provide it with its own 6 volt source with enough amps (like 4 * 1.5 V alkaline batteries). And your Arduino with USB power. Connect their grounds. Your servo should be fine with the 5 V signal on the signal line. If you want a common power source for each, create a 7.5 V power pack, which you connect to the barrel connector, then power the servo with the 5 V out from the Arduino. But in that case, your servo gets barely the minimum voltage.
Or try the 6 V power pack providing direct power to the servo and to the barrel connector. But 6V might be too little for the voltage regulator, which again means that the Arduino will work on too low voltage. Either you connect 5 V regulated to Arduino (like with the USB) or at least 7.5 V unregulated to the barrel connector (which Arduino regulates to 5 V).
Those 20Kg servos draw WAY too much power for the poor little regulator that drives the 5V pin. The best idea is to run the servo from a separate supply. You can use a DC-DC converter (at least 3A) from your 12V battery.
Or if you're going to use AA batteries as suggested then 4 x 1.2V NiMH rechargeables (Eneloop or similar) will work better and can run the Arduino directly as well as the servo (though at only 4.8V nominal you won't get the maximum power from the servo).
You can never us a resistor voltage divider to supply any power and certainly not the high power that your servo needs. And it's a bad idea to run any servo from the 5V pin and again THAT servo draws WAY TOO MUCH current. You will damage the Arduino.
There is no practical way to reduce 12V to a suitable voltage for the servo with just resistors or capacitors. If you really can't use a DC-DC converter then you need to stick with a MUCH SMALLER SERVO.
One DC-DC converter that might work is a phone charger you connect to a ciagreette lighter in a car. It might give 5 V and 1-2 ampere. Just get the circuit out of it, connect it to your 12 V battery and the 5 V to your servo and to your Arduino. You have to check how many amps your servo draws at 5 V and full load and that the charger can provide those amps plus the milliamps that your Arduino wants.
This BEC from Hobby King provides 20A. 12v in is withing its range. Selectable output voltage.
Search for BEC on their site (or AliExpress) for a large number of other sizes (and prices) of DC-DC converters.