Tolkien's history of Elves singing and Ents walking and talking

While not specifically answering when the Ents started to talk, this quote from Tolkien mentions that the elves didn't know where Ents came from, implying they actually existed before they sang to them (not such thing as Ents being awakened by Elves).

"No one knew whence they (Ents) came or first appeared. The High Elves said that the Valar did not mention them in the ’Music’. But some (Galadriel) were [of the] opinion that when Yavanna....besought Eru (through Manwe) asking him to give life to things made of living things not stone, and that the Ents were either souls sent to inhabit trees, or else that slowly took the likeness of trees owing to their inborn love of trees."

JRR Tolkien - Letter 247

It would seem strange that Ainur lost the abilitie to speak when embodied, but that's just my reasoning. However this quote seems to contradict the one you already quoted from TreeBeard in The Two Towers. Yet I'd like to add what Tolkien said about quotes from his characters:

"Treebeard is a character in my story, not me; and though he has a great memory and some earthy wisdom, he is not one of the Wise, and there is quite a lot he does not know or understand"

JRR Tolkien - Letter 153

Who talked first seems unknown, the best quote I recall about the Elves speaking is inconclusive:

"...and they began to make speech and to give names to all things that they perceived. Themselves they named the Quendi, signifying those that speak with voices; for as yet they had met no other living things that spoke or sang."

JRR Tolkien - The Silmarillion - Of the Coming of the Elves

Ents are likely older than Elves

On at least two occasions, Tolkien notes that the Ents are the oldest sentient race in Middle-earth (bold is my emphasis, italic is Tolkien's):

That is a long and yet bald resume. Many characters important to the tale are not even mentioned. Even some whole inventions like the remarkable Ents, oldest of living rational creatures, Shepherds of the Trees, are omitted.

^{The Letters of J.R.R. Tolkien 131: To Milton Waldman. 1951}

Ents. The most ancient people surviving in the Third Age were the Onodrim or Enyd. Ent was the form of their name in the language of Rohan.

^{Return of the King Appendix F I: "The Languages and Peoples of the Third Age" Of Other Races}

Appendix F goes on to suggest that the Elves awoke in Ents the desire to begin speaking, though the Entish language was of their own devising:

They were known to the Eldar in ancient days, and to the Eldar indeed the Ents ascribed not their own language but the desire for speech.

^{Return of the King Appendix F I: "The Languages and Peoples of the Third Age" Of Other Races}

The exact relationship between the Ents and the Huorns is indeterminate from Tolkien's writings¹, but it's clear that they are related, and were almost certainly created at the same time.

The Elves, for their part, are implied to have begun speaking (and singing) some time after their first awakening, not literally from their first moments:

Long they dwelt in their first home by the water under stars, and they walked the Earth in wonder; and they began to make speech and to give names to all things that they perceived. Themselves they named the Quendi, signifying those that speak with voices; for as yet they had met no other living things that spoke or sang.

^{The Silmarillion III Quenta Silmarillion Chapter 3: "Of the Coming of the Elves and the Captivity of Melkor"}

¹ Merry, of course, believes that Huorns are Ents that have "gone treeish"; but he, like Treebeard, is merely a character and not omniscient

Elves are Likely (Just) Older than Ents

Fourth option

This seems to be the correct sequence from my take on the information from the answer I accepted (see my comments below that answer also) along with the quotes given in the question and other answers here, but particularly how these things relate to the quote from Gandalf that sparked the question.

I felt a summary like within my question would be a fitting, useful addendum as an answer.

1. Trees were created (significant to the history of the Ents and Treebeard, see below*).
2. The second star creation occurred (significant to the history of the Elves).
3. Elves were created, but did not themselves yet talk, and in fact walked the earth under the stars without speaking for some time.
4. Ents were created (nearly simultaneously to Elves, but I think just after), as spirits summoned by Yavanna's awakened thought to inhabit some of the trees, and these Ents were walking from the start while also not speaking.
5. Elves began to talk and sing.
6. Elves taught (or awakened the desire in) Ents to talk.
7. The Huorns (likely) descend in some way from the lineage of the Ents after they could speak, for the Huorns also have a voice.

So the power that walked to which Gandalf refers is almost certainly the power of the Ents as Shepherds of the Trees, even before they were speaking.

That Ents are the oldest and most ancient of people (see my discussion under the accepted answer), my take is that the references are all in relation to the 3rd Age time frame. That is, Fangorn is the most ancient of any people group still surviving into the 3rd Age, and he belongs to the Ents. So through him, at the time of the 3rd Age, Ents are:

1. "oldest of living rational creatures" (emphasis added), i.e. the people group that still has a representative living as of the 3rd Age; I cannot imagine a non-living rational creature, nor do I think did Tolkien, and so that fact seems key to what is being stated in that quote from Letter 131 given in this answer.
2. "The most ancient people surviving in the Third Age" (emphasis added), i.e. the people group that still has a representative surviving as of the 3rd Age, which is Fangorn/Treebeard. The Elves had Círdan, and Tom Bombadil is not part of any "people" per se.

But also, see further thoughts related to "oldest" below.

* The quote from the Treebeard entry on Tolkien Gateway says:

Treebeard was the eldest person of Middle-earth, obviously being created along with the Ents during the Years of the Trees [me: but this is not so obvious, per the whole discussion here], before the creation of the stars; although he said that there were trees in Fangorn that were "older than he" [bold added].

The last statement actually fits with the time frame above and with the fact that spirits were summoned upon the awakening of the Elves to inhabit trees. So now we end up with some possible "overlapping" time frames for Treebeard even, namely:

1. Treebeard's tree "body" (hröa) likely existed before the Elves creation, then...
2. His "spirit" (fëa) joined the body, which occurred just after Elves awakening.

In this way, he is both "older" than Elves (in body), yet slightly younger than the Elves as a sentient combined body/spirit being (but as of the 3rd Age the oldest of any such species still surviving), and thus still younger than some of the trees in Fangorn forest that did not become Ents.

There's at least some reason to think the opposite. A key piece of evidence is from The Two Towers:

Treebeard recounts the ancient song of living creatures to Merry and Pippin:

Learn now the lore of Living Creatures!
First name the four, the free peoples:
Eldest of all, the elf-children
Dwarf the delver, dark are his houses
Ent the earthborn, old as mountains
Man the mortal, master of horses:

So both Treebeard and the source of the song credited elves as the oldest of the four free peoples, which explicitly includes Ents.

Maybe there's a way to resolve this, but it's not easy.