An excellent and very astute question! Thanks for trusting us with an answer.
The passing of a "year" has always been determined by when the sun reappeared in front or a particular set of stars. It might sound funny describing it that way, but when a particular star appears on the horizon opposite the sun at sunset, or a particular star is no longer visible in the dusk in the West at sunset, these are all reliable markers of the completion of a year or the beginning of a new year. Of course, in the time of Julius Caesar, the calendar in use was the Roman calendar, and the Romans did the very same thing - observe the stars. By observing the stars, sun, and moon, they determined when a year was completed or beginning, but how years were counted is an entirely different matter.
It's hard to speak definitively of the numbering of the years in those days because the historical record is sparse. But "years" in the time of the Roman Empire were not actually counted from any fixed origin. Instead, they counted the number of years of Roman Consul in power. So the Romans actually referred to their years as the "year X of the Roman Consul of so-and-so".
Amongst the many problems of the Roman calendar was a very poor reconciliation of the Equinoxes. The Vernal Equinox is important as it marks the spring, and the Autumnal equinox marks the beginning of autumn. These are two, key periods in the year - readily identifiable by the positions of the stars compared to the position of the sun. There were many attempts by the various rulers of Rome to "fix" the calendar so the equinoxes were correct, but not often with sound results as politics an mysticism entered into the determinations.
For example, there was a time when the number of days in each month were intentionally made "odd" because "odd" numbers were considered to be lucky. They had great difficulty accounting for lunar months, while reconciling that the solar year did not match the lunar year. At one time they had, for example, a year of 10 months, but included a period of "winter" which had no name but was required to keep their "year" in sync with the sun.
Eventually, the Roman Calendar had 12 months, but still an intercalary month was required few years to keep the solar year in sync with the Vernal Equinox (which defined the tropical year). This all seems very strange to us today if for no other reason than today we simply do not need to think about what day, month, or year it is! But think of the time of Rome, when you must plant when the season is right, but your "calendar" says one thing, while stepping outside, the temperature and the position of the sun say something entirely different!
By the time of Julius Ceasar, they had accumulated enough knowledge of the sun, the moon and the tropical year to realize that the Roman calendar was all messed up. So in the time we now call "46 BCE", Julius Ceasar reformed the calendar to have a fixed 365 day year, but to keep the Vernal Equinox in sync with the sun a "leap day" was added every 4 years. It is historically interesting that even in the Julian reform, they still messed up the counting of leap years, and inserted too may leap days which had to be fixed by the time of Julius Augustus who succeeded Julius Ceasar. Nonetheless, the counting of years simply continued by the counting of the "year of the emperor in power".
This counting of years from the year of the emperor in power continued in the Roman Empire until a fellow named Dionysius Exiguus, a Roman Monk, came along who attempted to calculate the number of years it had been since the birth of the Messiah! This was completely tied to his determination of the date of Easter! (You see, Dionysius did not approve of the method used by the Church of Rome to determine the date of Easter. It's an interesting study of the reasons behind the efforts of Dionysius Exiguus to reform the computations of the Church, but well beyond the scope of this text).
Though records are far from complete as to how Dionysius made his calculations, it is recorded that it was in the "present year of the consulship of Probus Junior Flavius Probus" that he determined was 525 years "since the incarnation of our Lord Jesus Christ". Thus, that year of the consulship of Probus Junior became the year "525 Anno Domini", or "the year of our Lord 525". So Dionysius calculated a new table for the dates of Easter for many years into the future, which were relatively quickly adopted in Rome, and over time, perhaps 200 years, the numbering of the years based on the year of the birth of the Messiah took hold. Therefore our current era, measuring the number of years since the Messiah's birth, can be attributed to Dionysius Exiguus.
All the above was necessary to answer your first and 3rd question, to wit "When did the counting of years begin?" an "Who was responsible?" The answer is "in the year 525". And Dionysius Exgiguus was responsible, for it was determined by Dionysius that the "present year of the consulship of Probus Junior Flavius Probus" was 525 years since the birth of the Messiah.
Now, part of your next question, about the "year zero" issue, is already answered. If Dionysius determined that the year of the consulship of Probus Junior Flavius Probus was 525 years after the birth of the Messiah, then years previous to the year of birth would necessarily have to be negative. Unfortunately, the record here is just as murky as the counting of years.
Dionysius himself did not start numbering years after his calculations as "526", "527", etc. because it remained the norm to number the years as the year of the rulership of the current emperor. Some 200 years later, an English cleric named "Bede" wrote a history, the "Ecclesiastical History of the English People" in which he made an attempt to reconcile certain historical events to the year of the creation of Rome, and while he was at it, he used Dionysius' determination of the year of the birth of the Messiah, so his years often included both "the year since the creation of Rome", and "the year since the incarnation of our Lord."
In his works, he also spoke of earlier years as "before Christ". Thus, to simplify the particular details, in the 200-300 years after Dionysius determined that it had been "525 years since the birth of the Messiah in that particular year of the rulership of Probus Junior Flavius Probus", the idea of simply counting the years since the birth of the Messiah was catching on.
Bede did not use a "year zero" in his writing and it is typically incorrectly stated that he did not know about the number zero. We know the Arabic numeral for zero (0) did not enter into common use in Europe until the eleventh century, and Roman numerals had no symbol for zero, but Bede and Dionysius did know of and use a Latin word, "nulla" meaning "nothing" whenever Roman numerals or Latin numbers for "zero" were needed where a modern "zero" would have been used.
So it seems that Bede made a conscious decision that when referring to the years before the birth of the Messiah, he would talk about the "first year" before, or the "2nd year" before, etc., and that he understood there would be no such thing as the "zeroth year" before the birth of the Messiah. In this regard, Bede was absolutely correct! The year before the Messiah's birth would be the 1st year not "zero", as we begin counting, either forwards or backwards with the numeral "1", not zero. The zero becomes important only when we must perform mathematical computations.
Though it is not likely provable, it is almost certainly clear that this is the origin our our term "BC". Thus, the years of "after the birth of Christ" became "AD" (Anno Domini), the years before became "BC". It is only in our modern, politically correct era that "AD" became "CE" (meaning "common era") and BC, rather than meaning "Before Christ", became "BCE" or "before common era" in an attempt to remove anything of "God" in society. But only astronomers require the use of a "year zero" and only to permit easy math. Thus any year "BC' or "BCE" is, in astronomical terms, simply converted to a negative, and reduced by "1", so for example, "500 BC" is "-499" in astronomical terms. Thus, no year is "missing" as you suggest.
Neither the Julian nor the Gregorian calendars use a "year zero", and one must be careful when computing ancient years to take this into account. This is why in Andrew Roth's "Wheel of Stars" he says that one needs "anchor dates" to determine the actual period in which an ancient event happened, such that the event can be tied to an astronomical event, which can then be firmly fixed to a Gregorian date - even though the Gregorian calendar did not exist at that era of humanity. What Andrew was able to do, is basically say that for Biblical event X, the Gregorian date would have been such-and-such, had the Gregorian calendar existed at that time.
He did this using a Gregorian calendar spanning 8000+ years, well into the past to 3501 BCE , against which he was able to match key Biblical events requiring the sun to be in a particular part of the sky which then accurately matched the date as described by the Gregorian calendar had the Gregorian calendar been in use at that time in history. When Andrew refers to ancient dates in "Wheel of Stars", it is true the Gregorian calendar did not exist when those events took place, but he has accurately described those events using the date it would have been had the Gregorian calendar been used at that time.
Applying a calendar before the calendar existed is referred to as a "proleptic" calendar - and is, as far as I know, unique here as Andrew has used it. Most authors simply use the Proleptic Julian calendar as they refer to dates back in ancient times, but the Julian calendar becomes terribly inaccurate as one goes back in time, just as it became terribly inaccurate as time progressed forward in the era in which the Julina calendar was in common use! This was the very reason for the switch to the Gregorian calendar in 1582!