Of the named Elves it's almost certainly Cirdan, who was on the Great Journey and possibly even dates back to Cuivienen.
Note 29 to the Cirdan essay in HoME 12 confirms the former:
Before ever they came to Beleriand the Teleri had developed a craft of boat-making; first as rafts, and soon as light boats with paddles made in imitation of the water-birds upon the lakes near their first homes, and later on the Great Journey in crossing rivers, or especially during their long tarrying on the shores of the 'Sea of Rhun', where their ships became larger and stronger. But in all this work Cirdan had ever been the foremost and most
inventive and skilful.
There are several possibilities for Elves that are even older than him, however. We know (from Quendi and Eldar, published in HoME 11) that of the First Kindred all became Eldar (i.e the Vanyar) and none became Avari. Of the Second Kindred the split was 50/50, with the half that became Eldar being the Noldor. The other half of the Second Kindred remained in Middle-earth. Of the Third Kindred about two-thirds became Eldar with the rest remaining as Avari.
From there occasional groups dropped off in the course of the Great Journey (most notably at the Misty Mountains) and about another third of the Third Kindred remained as Sindar.
Aside from the First Kindred (who all went to Valinor) it's never said what happened to the original Elves that awoke of the Second and Thirds. We know that Finwe and Elwe were not among the original 144, but what we don't know is how many of those remained as Avari. If we assume that at least some did, and if they're still alive, then they would be the oldest Elves in Middle-earth.
Edit to Add: Some dates from the Annals of Aman (HoME 10), all given in YT (Years of the Trees; 1 YT = approx 10 Years of the Sun):
- 1050: The Awakening of the Elves.
- 1085: Orome finds the Elves.
- 1090: The Battle of the Powers begins.
- 1099: The Chaining of Melkor.
- 1102: Ingwe, Finwe and Elwe as Ambassadors to Valinor.
- 1105: The Great Journey begins and the First Sundering.
- 1115: The Great Journey at Mirkwood/Greenwood, Anduin and the Misty Mountains.
- 1125: The Vanyar and Noldor reach Beleriand.
- 1128: The Teleri reach Beleriand.
- 1130: Elwe is lost.
- 1133: The Vanyar and Noldor reach Valinor.
- 1149: Cirdan is lord at Brithombar and Eglarest.
- 1151: The Teleri reach Tol Eressea.
- 1179: Birth of Feanor.
- 1190: Birth of Fingolfin.
- 1362: Birth of Galadriel.
Update - 13th March 2015
Next oldest after Círdan is almost certainly Daeron. He was the Loremaster and Minstrel of Thingol, and the Annals of Aman state that he invented his runes in VY 1300. That means that he was born sometime earlier, obviously, but we don't know how much earlier.
Now, in Of Beren and Lúthien we read:
But seeking for Lúthien in despair he wandered upon strange paths, and passing over the mountains he came into the East of Middle-earth, where for many ages he made lament beside dark waters for Lúthien, daughter of Thingol, most beautiful of all living things.
This establishes a good probability that Daeron is still alive in the east of Middle-earth at the time of Lord of the Rings.
Maglor, of course, is probably also still alive (and notably the last of the Fëanorians), but we don't have a birth-date for him.