With respect to this statement from Galadriel...
"He has dwelt in the West since the days of dawn, and I have dwelt with
him years uncounted; for ere the fall of Nargothrond or Gondolin I
passed over the mountains, and together through ages of the world we
have fought the long defeat."
Where is "the West" where Celeborn dwelt? Aman is probably not meant, but otherwise it's fairly vague with respect to Middle-earth. Galadriel does not specify which mountains she means, and does not actually say that she fled Doriath at this time.
I realize there was another probable meaning behind this statement at the time Tolkien wrote it, but is it impossible that Galadriel might mean she first arrived in Doriath after passing over some mountains, considering the path of the Exiled Noldor when they came to Middle-earth?
Admittedly, it might seem odd to say "before" the fall of Nargothrond or Gondolin if she "arrived" in Doriath before even the founding of Nargothrond...
... on the other hand she is speaking to the Company here, with Hobbits among them. It's not history class. The Fall of Nargothrond and Gondolin could be a very general time reference, not meant to be any more specific that to suggest "a long long time ago", and to provide a point of historical reference, perhaps in the way people might say today that something happened before the Fall of Rome, even if that something happened before the founding of Rome.
Not that it proves my characterization is true of course, but to note another reference (the poem did not format the way it's printed in the book):
"The world was fair, the mountains tall,
In Elder Days before the fall
Of mighty kings in Nargothrond
And Gondolin, who now beyond
the Western Seas have passed away:
The world was fair in Durin's Day."
Anyway, in texts written after The Lord of the Rings was published, after the First Age Galadriel and Celeborn pass ultimately to Eregion. And in 1967, in The Road Goes Ever On, this is confirmed in publication, if briefly. Here the mountains are specifically noted:
"After the overthrow of Morgoth at the end of the First Age a ban was
set upon her return, and she had replied proudly that she had no wish
to do so. She passed over the Mountains of Eredluin with her husband
Celeborn (one of the Sindar) and went to Eregion."
JRRT, The Road Goes Ever On
I think the arguable suggestion is that they both end up in Lindon after the War of Wrath, just like other Elves from Beleriand. If so, where were they earlier?
One might guess: for the most part in Doriath, before its fall.
But Tolkien never really completed, fully at least, his Silmarillion, especially the end chapters. And he doesn't goes into detail about Galadriel after a given point in the Quenta Silmarillion tradition itself. There is, however, an interesting comment from Christopher Tolkien in Unfinished Tales...
"It is a natural assumption that Celeborn and Galadriel were present
at the ruin of Doriath (it is said in one place that Celeborn "escaped
the sack of Doriath"), and perhaps aided the escape of Elwing to the
Havens of Sirion with the Silmaril -- but this is nowhere stated."
CJRT, commentary on Celeborn, The History of Galadriel and Celeborn
At the moment I'm not sure what "in one place" refers to regarding a specific text, but if Celeborn escaped the sack of Doriath, one would think Galadriel might have been with him. Then again, this is just a tantalizing note, written at some point, about Celeborn.
In the very late, adumbrated tale, we have a different history: Galadriel is removed from the Rebellion, and with Celeborn (here a Telerin Elf from Aman) they reach Middle-earth sooner than Feanor, sailing into the haven where Cirdan was lord. In the "years after" they did not join in the war against Angband, and their counsel was to withdraw from Beleriand and to build up power to the eastward, and both "... departed over Ered Lindon before the end of the First Age; and when they received the permission of the Valar to return into the West they rejected it."
My problem with some of this is that it conflicts with already published text (published by the author himself): Galadriel was not only part of the Rebellion but was banned for her special role as a leader of the Noldor (she helped lead them into the North and over the Grinding Ice). And Celeborn was Sindarin, as noted in the above quote.
So I disregard the late "adumbrated" version and try to square the two author-published descriptions: the statement from The Lord of the Rings (Galadriel passing over "the mountains" before the fall of Nargothrond and so on), with the explicit statement that she with Celeborn passed over the Blue Mountains after the fall of Morgoth and the ban (and so on), and went to Eregion.
Admittedly, my attempt above is not perfect, as I say.
And in the end the question still remains.
If you take Galadriel's statement from The Lord of the Rings to mean she left Doriath before the fall of Nargothrond and met Celeborn [once a Nandorin Elf] already in Lorien (again, which was arguably the underlying conception in any case, at the time it was written, according to Christopher Tolkien in Unfinished Tales), or if you consider her words there vague enough to allow another interpretation, especially considering other factors (Celeborn being Sindarin in an author published account, for example)...
... the answer to this particular question remains misty so far!