Paidion’s report is a good one (and I have a little more regard now for J,F,B’s notion of it being a “contracted expression”, although I think they’re applying the wrong terminology in calling it that.)
However, I can solve much of the problem even without regard to 2 Tim by noting that in the Greek the word isn’t “promised” but PROMISES in the middle voice form. While that can plausibly mean past tense, and past tense could also be included in the scope, it also can be the verb form for divine ongoing action (top down at a right angle to all of natural history, so to speak): God is promising. (Middle voice form doesn’t necessarily have anything to do with timing one way or the other, which makes it ideal for speaking of divine timeless action. But it can mean past action, too, even for God.)
{pro}, meanwhile, not only means “before” in the sense of physical time and space, it also can have the meaning of “before” in the sense of importance. (I was hoping before I looked it up that the term was actually {pros}, which would involve God promising life eonian to the times eonian, seeing as that would hugely solve a lot of problems–and would count as weight toward universalism, too. 
But I can’t in honesty do that, it’s {pro}.)
The gist then would be the same as if Paul had written that God promises life eonian from above the highest heaven. And once more this could be ratified if {aionion} should mean ‘from God’ and not merely a never-ending sequentiality, as not only "zoe eonian but also “chronon eonian” both in their own ways imply. The life is from God and the times are from God, and the promise is from the God Who gives the life and gives the times.
The comparison with 2 Tim, however, is certainly helpful and instructive, too, as there are parallels beyond the use of the same prepositional phrase:
2 Tim 1:9-11 God saves and calls us not in accord with our acts “but in accord with His own purpose and the grace that is given [act verb form] to us in Christ Jesus before times eonian, yet now is being manifested through the coming of our Savior, Christ Jesus, Who indeed abolishes death yet illuminates life and incorruption through the evangel into which I was appointed a herald and an apostle and a teacher of the nations.”
Titus 1:1-3 “[from] Paul a slave of God and an apostle of Jesus Christ in accord with the faith of God’s chosen (ones) and [in accord with] a realization of the truth, which accords with devoutness, on the expectation of life eonian, which God, Who does not lie, promises [middle voice form] before times eonian, yet manifests His word in its own eras in heralding, with which I was entrusted, according to the injunction of God, our Savior; to Titus etc.”
The verb form of “given” in 2Tim is that of an ongoing (sometimes also thus an incomplete) action, still going on at the present time; the verb form of “promises” in Titus 1 could be a divine timeless (by use of the middle voice form). The grammatic structure of the 2Tim reference is definitely such that past times in chronology are not being referenced but rather action from above at all times; and the grammar for Titus 1 could easily be meant that way as well. Note also that in 2 Tim the topic of that being given from times eonian is grace which is topically explicit to be by the divine choice and not due to any action of ours, thus also not due to any action of ours in time.
Strengthening the idea that the same notion is meant in both verses, is that the basic notional structure is identical across both claims being made by Paul. In 2 Tim, the action of grace is given from a position superior to time, yet is manifested in time by the coming of Christ Jesus, Who yet acts in a timeless fashion within time (so to speak), in comparison to the appointment of Paul in past time to join in the heralding of the gospel. In Titus, the action of the promise of eonian life is promised from a position superior to time, yet God manifests His Word (a title for Christ) in its own eras (of time) for heralding, in comparison to the appointment of Paul in past time to join in the heralding of the gospel.
If the position superior to time in 2 Tim involves a timeless ongoing action still going on today (or anyway at the time of Paul’s composition of the epistle), which the verbal grammar and the context definitely involve; and if the position superior to time in Titus 1 could grammatically involve a timeless action-state of some sort, in a sentence with otherwise strong compositional similarities to a sentence where the relative time issues are definitely not about a promise being given merely in times long past; then we have strong exegetic reason to believe that in Titus 1 Paul meant the same timeless action relationship.
That being said, there isn’t any direct exegetical reason to disallow the notion of God making a promise to someone about life eonian for us “before” natural time either. Neither is there anything in the verse to positively indicate who God would be making the promise to. (It could be to Christ, but that would be based on reading this in from other scriptures, not on exegesis of the verse directly.)