The ancient Greeks themselves called the paradigmatic stories they told about the past mythoi, "spoken stories". The original meaning had no necessary implication that these "myths" were religious in nature, nor necessarily untrue. On the other hand, that doesn't mean you'd necessarily believe them: anyone could make up a mythos and tell it as an allegory for something they just thought of. This is something that Plato does fairly often -- his mythoi about the cave, the divided line, Atlantis, Er, and indeed the entire Republic are basically ad hoc mythoi designed for some purpose or other.

The relationship between "myth" and "religion" is one that will depend on context, as everyone means something slightly different when they use these words. "Religion", in particular, is a word that's very hard to pin down: does it mean (a) personal beliefs? (b) dogma authorised by some central religious authority like the Vatican? (c) stories about the divine realm and past figures who were close to the divine realm? (d) contemporary places, people, and practices associated with the religion? or (e) something else?

I find it useful to opt for (d), the practice of religion. Here's why. (a) is arbitrary (whose personal beliefs? the guy in the second pew from the front, or the woman behind him?) and ultimately unrecoverable, because we can't read minds. (b) is important, but not necessarily essential, as not all religions have central authorities, and even if they do, that authority may not be representative of how the adherents of the religion think about it. If you define religion as (c) stories about the divine realm and past figures who were close to the divine realm, then trivially there will be no distinction between religion and myth, so the conversation's already over. But (d) deals with the tangible: material culture, physical spaces, documented practices -- in short, recoverable historical data.

If you follow me in this, then it will follow that mythology and religion are talking about different things. A mythology is not a dead religion. Especially in the context of ancient Greek religion, religious practice varied wildly all over the place, and was dominated by local shrines and regional cults; Athena was important in Athens, Hera in Argos, Apollo in Delphi and Delos, Zeus in Dodona and Crete, Hades and Zeus in Elis, and so on. The worship of Persephone and Demeter at Eleusis (near Athens) was something quite separate and different from the worship of Persephone and Hades in Epizephyrian Lokris (southern Italy).

But while religious practice was extremely diverse, some of the most important myths about divine and near-divine figures were effectively the common heritage of all Greeks. Many myths changed wildly according to local customs (e.g. on Ithake, Penelope is the wife of the exiled Odysseus; in Mantineia, she's the mother of the god Pan), but there was a lot of common ground, and starting very early on, the ancient Greeks tried very hard to synthesise them into a coherent body of consistent narratives. Pan-regional narratives emerged, with the ambition of becoming pan-Hellenic, at the same time that the religious festivals of certain religious sites took on a pan-regional or pan-Hellenic scope (festivals at places like Olympia, Delphi, the Isthmos, and Delos). These are the ones that ended up becoming most "canonical", even in the absence of a system for enforcing religious belief, and stayed fairly consistent throughout antiquity. But the local cults continued too, so we see lots of variation after that time too: for example, throughout the Archaic and early Classical periods, when Sparta and Argos were competing for political hegemony in the Peloponnese, one tactic that they both used was to try and build the cultural hegemony of the foundation myths of their common ethnic group, the Dorians.

Anyway, with this approach, religion means "religious practice", and mythology means "a body of narratives, some of which underlie local religious practices, others of which are common cultural heritage". So, to get back to your original question, they were never a belief system as such: belief was never the important thing. Belief was only relevant to the local cults, and the local stories. The truly pan-Hellenic myths were never part of anyone's religious practice; they were there because they constituted a cultural heritage that everyone had agreed to share. That way, even when the religious practices die out, the myths live on, because the cultural heritage isn't going anywhere.

This is a real problem with the English language. Too often, we use "mythology" to mean "other people's religions." When teaching folklore, I have frequently been asked about "Indian myths." This is, in fact, insulting. Once I had a graduate student who was a Native American, and I asked her how she felt about that sort of question. She said she found it terribly insulting. We would expect a Christian to be insulted if we asked about "Resurrection myth" and yet too many people don't think twice about asking about the "coyote myth" and the origin of some aspect of humanity. These stories are dear to Native Americans, and there are some who maintain pre-contact belief systems.

There is less of a chance, of course, of offending an ancient Greek believer in a 4th century BCE religion by calling ancient stories "myths," and yet the term carries with it a certain presentism and elitism: "they" believed in silly superstitions and outrageous stories, that "we" have long since left behind.

Here are several paragraphs from an Introduction to Folklore that I am putting together; the excerpt may help:

Something needs to be said here about myth. People use this term awkwardly. In a European context, myths tend to be the artificial constructs of ancient and Classical-era priests or literate people who sought to weave folk traditions into a comprehensive whole. The exercise often had political purposes, designed to provide diverse people with a single set of beliefs and stories. By reconciling similar traditions, the shared culture of these groups could be seen as more important than the differences, justifying the central rule of the king and his priests. Myth is also a way or organizing and reconciling folk beliefs, which by their nature can be contradictory and highly localized. Myth tends, however, to make gods of supernatural beings, giving those powerful entities a status – for modern readers – similar to the Judeo-Christian God, even when this comparison is not justified.

In general, the word myth is best set aside when discussing more recent folk belief, recognizing its proper status as a literary genre. Nonetheless, ancient documents recording myths can assist in the understanding the history of various stories and beliefs. The authors of these texts were, after all, the first folklorists, and they were the only ones coming close to practicing the craft at the time.

Some folklorists carelessly use the term myth to denote those legends that deal with a fantastic, remote time. This primal era saw the creation of many familiar things such as day and night, fire, people, mountains, and all other aspects of the present world. Folklorists properly refer to these stories as etiological legends, that is, Sagen explaining the origin of things. Sometimes, however, people interchange etiological legends with the word myth. The problem with this is that “myth” denotes something that is from a previous period, inherently wrong, and linked to “primitive” superstitious beliefs. When the term “myth” is used for the folklore of existing cultures or for the traditions that were viable only a generation or more ago, it carries with it an insulting, derogatory tone. It is best to reserve the word “myth” for ancient and Classical-era texts.