Answer
The answer is given in the very next verse itself.
“on hope of eternal life which the God who does not lie promised
before the eternal times, BUT REVEALED in its own times in a
proclamation of His Word” (Titus 1:2-3).
Explanation
So, we see that God made the promise to Himself (i.e., He planned it) before the eternal times, that is, to scientifically speak, ‘before time began’.
But this promise was revealed later, that is, again to use the scientific jargon, ‘after time began’, in the due time, especially when He started to proclaim His Word through Moses and the prophets.
Do we see any mention of such promise?
Yes.
“It is like the dew from Mount Hermon, falling on Zion's mountains,
where the LORD has promised to bless his people with LIFE
forevermore.” (Psalms 133:3).
Zion is the representative figure of Jerusalem that is the capital of the Promised Land. So God made His promise of eternal life to His people in the mountains near Jerusalem.
Again, do we see any such incident in the Old Testament (which the OP insists to find out)?
Yes.
“I call Heaven and earth to witness against you today that I have set
before you LIFE and death, the blessing and the curse.
Therefore, choose LIFE, that you may LIVE, you and your seed”
(Deut 30:19).
Oh, where are the mountains of Zion involved here?
“And it shall be when Jehovah your God shall bring you into the land
(of Zion) to which you go to possess it, that you shall set the
blessing on Mount Gerizim, and the curse on Mount Ebal” (Deut
11:29).
There it is.
God gave a promise and a choice to Israel.
[The details of how to do it are given in Deuteronomy 27:12-26. The actual thing took place in Joshua 8:30-35.]
Same Promise to Adam & Eve
The same God has given the same promise to the first human beings also:
“And out of the ground Jehovah God made to spring up every tree that
is pleasant to the sight, and good for food. The Tree of LIFE
(life eternal) was also in the middle of the garden; also the Tree of
the Knowledge of Good and Evil (death)” (Gen 2:9).
The same God gave the same choice to them too.
“And Jehovah God commanded the man, saying, Eating you may eat of
every tree in the garden; but of the Tree of the Knowledge of Good and
Evil you may not eat, for in the day that you eat of it, dying you
shall die” (Gen 2:16-17).
Adam and Eve could eat from every tree including the “Tree of LIFE” which was a blessing. The only prohibited tree was the tree of curse. But unfortunately, human history took a cursed turn.
But God’s promise is open still to human beings. God renews it through Prophet Jeremiah:
“And you shall say to this people, So says Jehovah, Behold, I set
before you the way of LIFE and the way of death” (Jer 21:8).
Conclusion
So God planned (promised Himself) the eternal life for humans before time began but He revealed it later when He started to write down His Word through His prophets.
We see the promise right from the Garden of Eden and onwards continuing in the New Testament through the Gospel of Jesus Christ.