Your first suggestion seems spot on:
"ante urbem conditam" is correct and has several classical examples.
Cicero provides the most convincing example of this usage:
itaque et illos septem, qui a Graecis σοφοί, sapientes a nostris et habebantur et nominabantur, et multis ante saeculis Lycurgum, cuius temporibus Homerus etiam fuisse ante hanc urbem conditam traditur, et iam heroicis aetatibus Ulixem et Nestorem accepimus et fuisse et habitos esse sapientis. (Cicero, Tusculanae Disputationes, V, 7)
And so we have received these seven, who were held and esteemed as "sophoi" by the Greeks and "wise" by our own, as well as Lycurgus many centuries before the founding of this city, in whose times Homer is even said to have lived, as well as Odysseus and Nestor in heroic ages--we have agreed that these men lived and were held to be wise.
In this example, I think it is debatable and potentially important to the spirit of this question whether "multis ante saeculis* is meant to quantify "ante urbem conditam* or not.
One other natural place to search was Livy's Ab Urbe Condita, which quickly yielded the following phrase in the preface to chapter I:
quae ante conditam condendamve urbem poeticis magis decora fabulis quam incorruptis rerum gestarum monumentis traduntur, ea nec adfirmare nec refellere in animo est.
Canon Robert's translation:
The traditions of what happened prior to the foundation of the City or whilst it was being built, are more fitted to adorn the creations of the poet than the authentic records of the historian, and I have no intention of establishing either their truth or their falsehood.
I will continue looking for specific examples of a "X specific time ante urbem conditam", and will update this answer with my findings.
Update
After some considerable searching, I found an example from Marcus Velleius Paterculus (19 BC - AD 31), who is squarely on the border of the Golden and Silver age though he is usually classified as the first author of the latter age. He includes the following phrase in his History of Rome:
Hoc tractu temporum ante annos quinque et sexaginta quam urbs Romana conderetur, ab Elissa Tyria, quam quidam Dido autumant, Carthago conditur.
In this time-period, sixty-five years before the city of Rome was founded, Carthage was founded by Elyssa of Tyre, whom some call Dido.
This certainly does not read as a formulaic way of telling time, but I believe in this respect @Ilmari Karonen's observation is very apt: there was generally very little history that could be precisely dated, using the historical methods at their disposal, before the founding of the Rome. Note that even this "sixty-five" figure is one of at least three proposed figures.
Some more variations and examples from Augustine, who is admittedly not in the Latin golden age but whose Latin--in general--is reminiscent of the best:
Tot bella gesta conscripta sunt uel ante conditam Romam uel ab eius exortu et imperio, Augustine, De Civitate Dei, I, 2
Nam hunc Homerus de stirpe Aeneae, a cuius posteris Roma est, cum ante illam urbem conditam idem poeta fuisse dicatur, inducit magnum aliquid diuinantem Augustine, De Civitate Dei, III, 2
*Maius
mensis in compluribus civitatibus Latinis **ante Urbem
conditam** fuisse videtur. Qua ex causa, utrum a ma-
ioribus, ut Iunius a iunioribus, dictus sit; an a Maia, quod Mercurio filio eius res divinae fiant sollemnes;
– Cerberus Apr 13 '16 at 14:59an quod ipsi deae in multis Latinis civitatibus sacrificia fiebant . . .*