Is there a backstory that explains how John Connor got an intact Terminator to reprogram and send back in time?
The Terminator: "My mission is to protect you."
John Connor: "Yeah? Who sent you?"
The Terminator: "You did. 35 years from now you reprogrammed me to be your protector here - in this time."
Short answer; he got it from the same place Skynet got it from.
Long answer; In James Cameron's original script there was a much more substantial "future prologue" sequence. In it is depicted the final battle against Skynet (remember, in T1 Kyle said that they'd won) and the capture of the time displacement complex. Inside, right next to the displacement chamber are racks and racks of inactive T-800s in cold storage, with a single unit missing (the one from T1, already sent back.) The scene ends with Conner standing in front of and staring at the next one in line.
You can check out and excerpt from the script here.
This was never outright stated, but it was heavily, heavily implied by the time the Sarah Connor Chronicles was canceled that there is no reprogramming going on. The Resistance is just not yet ready to believe that Skynet has its own rebels.
2x19, Today Is The Day, Part 2 was, I think, our first direct clue. Here's an extract from the Terminator wikia on the page for Catherine Weaver:
While underway back to the United States, a group of soldiers went to a storage locker to examine the mysterious box that had been recovered. Although Queeg claimed to have been instructed by John Connor to do this, the crew did not trust him and so opened the box. Discovering a liquid-metal T-1001, Goodnow raised her firearm and was killed. In the process, the Terminator took her appearance and escaped by slithering through an air vent.
Before Jesse Flores managed to leave the ship, which they are abandoning after Queeg is killed for refusing to comply with the crew's orders, the T-1001 delivers her message to Jesse, telling her that it is for John Connor. It is simply The answer is "No". Then the Terminator slithered away through the water. It is presumed that this T-1001 went back in time, replacing Catherine Weaver to take her place to create an AI that could be sympathetic to humans, giving them an advantage against Skynet.
The question posed to the Terminator was asked by future John Connor: "Will you join us?".
The question was repeated again in the series finale. Weaver had Ellison deliver it to Cameron, stressing very, very strongly that had to say exactly those words in that order, and that Cameron would understand what they meant.
And side note, since you didn't follow SCC very closely - I belieeeeve this was revealed to the viewers, but not the main characters, around the middle of Season 2:
Catherine Weaver was a liquid terminator who was building an AI named John Henry - an AI sympathetic to humans that would be capable of going one-on-one with Skynet.
Using T:Salvation as a reference, we know that they were capable of capturing hydro-bots. They knew enough at that time about the systems inside the bots to disable the radio transmitters which would alert SkyNet of the resistance's position. They probably knew more, possibly including the basics of how to interface with the chips which control the bots and may have been capable of reverse engineering some of the software to reprogram it, removing harmful code and replacing it with useful code.
If a T800 were encountered, it would have to be destroyed, or at the very least rendered harmless. Using knowledge gained from previous models SkyNet had developed, the resistance could also alter the code on the chips to become a useful ally. When reprogrammed, the T800 would then be rebuilt using spare parts from other terminators to create a working model. T800s are programmed to repair themselves, so the resistance wouldn't need to get it perfect, the T800 would be able to correct any flaws in the repairs made by humans.
As for the regrowing of tissue, this would probably have to be done at a facility SkyNet designed. T800s probably are unfleshed when working for the resistance in the future, just like we see on the battlefields in T2. Human tissue is only necessary for infiltration missions and time travel.
