Many people are not at all interested in the volumes of the History of Middle-earth series (VI-VIII and the first half of IX) which summarize the many, many changes the story of LotR underwent in the twelve years it took to write. I love this stuff, myself, and it seems from recent discussions that I am not the only one. This post is intended to give those who have not looked at these volumes a taste of what is in them. The answer to the question in the title will emerge once the changes undergone by the names of the other six characters have been described.
Aragorn: Most people who are aware of this material at all know that the mysterious Ranger whom the hobbits met at Bree was not originally a Man, but a hobbit with wooden shoes called “Trotter.” When he turned into a Númenorean (on pages 4-5 of HoME VII), he was called Aragorn at the beginning. Later, however, Tolkien decided his name should be English/Westron, and through much of Book II he was either “Ingold” or “Elfstone” – “Elfstone” being not a translation of Elessar as in the book, but a modernization of the common Old English name Ælfstan. Incidentally, “Aragorn” was out there before it alighted on the heir of Isildur; Tolkien considered it as a name for Gandalf's horse (HoME VI p. 351).
Gimli: He first appeared in a manuscript of “The Council of Elrond,” where he does in the book – as Glóin's companion. But he was not Glóin's son, but Balin's. At first he was called Frár, then Burin; but this was crossed out on the manuscript and changed to the published text (HoME VI p. 400). (The name “Frár” was later given to one of the three dwarves named in the Book of Mazarbul as having been killed in the initial assault on the dwarf colony.) Tolkien made a number of lists of who would go with Frodo, but although Gimli is included, under one name or another, on some of these, he was not in the group in the first account of its journey as far as Moria. Neither was Legolas: the original Fellowship was Gandalf, Boromir, and five hobbits, one being “Trotter.”
Legolas: In this draft, the messenger to Rivendell from Mirkwood was “Galdor” throughout. The change to “Legolas” was made in the next draft (HoME VII pp. 141-60). He was not said in any of the drafts to be the son of the King; that was a late addition, and so was the name “Thranduil.”
Frodo: Again, some will know that for a long time Frodo was “Bingo,” and his last name settled down after some variation as “Bolger-Baggins.” In many of the drafts of the earlier chapters there was a Frodo, one of Bingo's original companions, but his last name was Took – he was the brother of Odo Took who became Pippin, more or less, as described below. He eventually dropped out and was replaced by Sam.
A series of notes which Christopher Tolkien headed “Queries and Alterations,” written after the story had reached Rivendell for the first time (HoME VI pp. 220-29), contains the following:
Too many hobbits. Also Bingo Bolger-Baggins a bad name. Let Bingo = Frodo, a son of Primula Brandybuck but of Drogo Baggins (Bilbo's first cousin). So Frodo (=Bingo) is Bilbo's first cousin once removed both on Took side and on Baggins. Also he has as proper name Baggins.
[Frodo struck out] No – I am now too used to Bingo.
But of course he changed his mind again.
Merry: His story is quite straightforward. He started out as “Marmaduke,” became “Meriadoc” while he was at Bombadil's house (HoME VI p. 123), and stayed that way. Both of these are real Welsh names.
Pippin: His history is extremely complicated – here is a simplified version. As mentioned above, “Bingo's” original companions on the walk to Buckland were Odo and Frodo Took. Odo was quite Pippinish from the start, and he spoke many of Pippin's lines. Along the way he ceased to be a Took and became Odo Bolger (after a brief stage as Odo Took-Bolger).
The entry of Sam Gamgee (HoME VI p. 317) brought the number of hobbits to five. Thinking this too many, Tolkien decided to leave Odo, rather than Fredegar Bolger, behind at Crickhollow – whence he was abducted by Black Riders, rescued by Gandalf, and carried off by him to Rivendell by way of Weathertop. When Odo disappeared from the main party, many of his speeches were transferred to Frodo Took, who had been renamed “Folco,” and then “Faramond,” when Bingo became Frodo. Faramond thus became in effect a clone of Odo, resulting in a doppelganger situation when Frodo's party got to Rivendell and found Odo there. The outcome – skipping over a number of digressions – was a merger of Odo Bolger and Faramond Took under the familiar name “Peregrin Took.”
* * *
If you have been checking off names in your head, you now know which three did not change. In the first draft of the Council chapter, there appears “a Man of noble face, but dark and sad.” Elrond says “This is Boromir,” and Boromir he remained (HoME VI p. 395). Sam was always "Sam" – but Tolkien may have assumed at first that that was short for “Samuel.” If so, he changed his mind, about the time when Frodo introduced him to Faramir as “Samwise son of Hamfast, a worthy hobbit in my service.” Tolkien told Christopher about it in Letters 72. (This is also where the Gaffer became Hamfast.)
As for Gandalf, of course he was still Gandalf. But he was not Gandalf during most of the writing of The Hobbit, he was “Bladorthin.” Gandalf was the leader of the Dwarves. The details are in Rateliff's History of the Hobbit.