After the War of the Ring, Sauron = dead. Saruman = dead. Gandalf = has left on the ship. Elrond = left. Galadriel = left.
What was the oldest creature still alive in Middle-Earth in the Fourth Age?
Tom Bombadil. Per dear old Tom:
Eldest, that’s what I am. Mark my words, my friends: Tom was here before the river and the trees; Tom remembers the first raindrop and the first acorn. He made paths before the Big People, and saw the little People arriving. He was here before the Kings and the graves and the Barrow-wights. When the Elves passed westward, Tom was here already, before the seas were bent. He knew the dark under the stars when it was fearless – before the Dark Lord came from Outside.
Plus he's still alive at the end of Lord of the Rings (recall Gandalf saying he wanted to have a long talk with him at the end of Return of the King).
As should be obvious by now, in light of the previous answers, it is quite difficult to say with any certainty. The problem lies in the fact that Tolkien actually refers to both Treebeard and Tom Bombadil as "Eldest" (or at least allows his characters to do so).
Here is what the Tolkien Society has to say about it:
Who is older, Tom Bombadil or Treebeard?
Readers have noted that Gandalf says that Treebeard is “the oldest living thing that still walks beneath the Sun upon this Middle-earth” (p.499), and Celeborn calls Treebeard “eldest” (p.981). Although it is possible Celeborn may have been using the word more as a courtesy title than a statement of literal fact, Gandalf’s remarks seem harder to counter. However, Christopher Tolkien with ample justification has said on other matters that his father was fond of making hyperbolic statements, and this may be the case here. Perhaps Tolkien had forgotten that he’d used the adjective “eldest” for both Tom Bombadil and Treebeard.
There can be no doubt that Treebeard is old, but even he admits there are trees in Fangorn older than himself. However, when Tolkien refers to him as eldest he must mean that he is the oldest walking and talking sentient being in Fangorn. At one point Treebeard says that there are only three Ents left of those who walked in the woods before the Darkness. This must refer to the Darkness which entered into the world with Morgoth. However, Bombadil was present before the first acorn, which must predate the woods before the Darkness. Therefore, although it is difficult to be certain of Tom’s origins it is possible to argue with more certainty that Tom Bombadil is indeed the eldest of all the inhabitants of Middle-earth.
[page references are to The Lord of the Rings: 50th Anniversary Edition, 2004]
Tom Bombadil is not exactly a creature since he is not exactly a living being. Thus he might not count according to some definitions.
As I wrote in another question, Cirdan may have been the oldest elf at the time and he did not expect to leave Middle Earth until the last ship sailed sometime in the future.
Celeborn called Treebeard "eldest", implying that Treebeard was older than Galadriel and Celeborn and possibly the oldest pure biological being in Middle-Earth. Treebeard may have died before Celeborn left Middle-Earth, since it was stated that Celeborn (or a companion such as Cirdan) may have been the last person leaving Middle-earth to remember the Elder Days.