There's always more that can be said, but there's quite a bit in our FAQ about calendars.

The answer to the second bit of your question can certainly be found in the FAQs. As for the first bit, the Romans called AD 1 "C. Caesar L. Aemilius Paulus consulibus" - "the year when Gaius Caesar and Lucius Aemilius Paul's were consuls." This is how they had been naming years for as long as we can tell - the "ab urbe condita" (from the founding of the city) system was only invented by Varro in the 1st century BC, and never widely used.

Dating by chief magistrate or ruler was common across the ancient Mediterranean: in Athens it was the chief Archon, in Cyrene is was the high priest of Apollo and so on. Places that had monarchies might date by regnal years, so something like" in the 5th year of King so-and-so", and in fact the Romans came to do something similar by late antiquity, as the office of consul became less and less important.