How and When did people decide "This will be year 0"?
Surely the pre-Hellenic Greeks couldn't have known 'I live in 200 BCE, going downwards to 0', so what time period did they think they lived in?
Have there been any other serious attempts at making a new year 0?
There is no year 0.
BCE and CE are politically correct terminologies used by people today in a generally bald faced effort to remove Christian terminology from "secular time." Not that there's anything wrong with that, specifically, but that's the source of calling it the "Common Era" or "Before the Common Era."
BCE and CE replaced BC ("Before Christ") and AD ("Anno Domini": "Year of Our Lord"). It was calculated by the early Christians and codified into the Gregorian and Julian Calendars, and set as the starting point of the Christian Calendar, over and against the Jewish and Roman ones. Obviously the Greeks were not counting down the years until Christ's birth in Bethlehem. Before the Catholic Church basically standardized time across the West, most places used the reigns of Kings as their markers of time ("in the third year of the reign of Agrippa," or what have you). Christianity runs on a combination of solar and lunar calendars (that's why Christmas is always on the same date, while Easter moves around). Because Christ is the "King of Kings," the Church counted years moving outward from the birth of Jesus, rather than the births, deaths, and reigns of their earthly masters.
Other religions have similar ideas of starting points. Islam runs on a strict lunar calendar (which is 11 days shorter than our 365 day year), and it begins in what we call 622 AD, the year the Prophet Muhammad moved to Medina (so years now are XXXX AH, or "After Hijrah"). Judaism's calendar begins with the creation of the world, and was originally also a lunar calendar, but they later introduced a "leap month" called II Adar which adjusts their lunar calendar so that it more or less aligns with the solar one, and avoids the weirdness that Muslims face with their calendar not corresponding to seasons (for instance: Ramadan comes whenever it wants, which makes a huge difference if you're far from the equator and not eating from sun up to sundown).
The way any of these people figured out when those events happened was basically by counting genealogies. They would count the years of kings' reigns, births, deaths, etc. and work their way back through relative references until they had a decent estimate of when something happened. And it's worth noting that, in the Christian example, they did a pretty good job. As near as scholars can figure, Christ was born somewhere between 4 and 6 years earlier than (let's call it Pope Gregory XIII) calculated. Because of the recent drive to "secularize time" so to speak, and because it's confusing for Biblical scholars, theologians, and archaeologists to think of Jesus Christ having been born 4 to 6 years "Before Christ," we changed the names of BC and AD to BCE and CE, to delineate an arbitrary time to start numbering the years.
EDIT: I'm on my phone, so citing is hard.
There's an AskHistorians podcast about this. Happy listening!
There have been some previous threads collected on the FAQ page on calendars and timekeeping that you may find interesting: