In my opinion this is, unfortunately, not an adequate view. I use the term "unfortunately" here with full intent, because it really is unfortunate that the true distinction between science and non-science is something more abstract and not easily comprehensible to a layperson.
In fact the only possible demarcation between science and non-science is mathematizability. Scientific theories are those which could, in principle, arise from an underlying fully mathematical structure. This obviously includes evolution which arises inevitably from the molecular basis of life, which in turn arises from the purely mathematical theory of elementary particles.
By contrast, any theory which involves a god is inherently not reducible to mathematics. Indeed, this could be taken as the definition of a god; I doubt any believer's conception of god corresponds to an entity whose every aspect and action is governed by mathematical formulas.
If, on the other hand, the universe is not described by mathematics at the deepest levels, then there is no underlying structure and no point even talking about science. If there is no underlying structure then anything is possible at any time. Any regularity that we happen to observe and study with "science" is not a reflection of underlying order, which by hypothesis does not exist, but rather is just the whim of gods or something like that.
Personally, I think this scenario is not only incompatible with the existence of science, but actually impossible, because regularity is necessary for existence, and regularity comes only from mathematics. Hence, in my opinion, all universes which can possibly exist will have science, and all for the same reason, namely that they are founded on mathematics.
What about falsifiability? In the view I propose here, this is closely entwined with science, but not absolutely essential in all cases.
Note first that, absent a mathematical foundation, falsifiability is clearly impossible since it is impossible to formulate a falsifiable statement that is not compatible with reduction to mathematics. A falsifiable statement is something like "95% of chicken eggs have one end more pointy than the other". This statement is compatible with reduction to mathematics because, in fact, it arises in our world through the mathematical theory of the atoms from which chicken DNA and whole chickens are built. In general, any falsifiable statement must reflect a regularity of the universe which we can observe, and any such regularity is compatible with reduction to mathematics, since mathematics consists of the study of all regular structures.
Non-falsifiable statements, unfortunately, are not quite so simple. They fall into two types (that I am aware of). The first involve entities such as gods which, by definition, are not reducible to mathematics. They can never be falsified because the entities involved are not, by definition, governed by any kind of mathematical laws, and hence they don't obey any rules that could conceivably be tested. They just "do what they want" (except that, as I mentioned above, I don't believe that can exist at all).
There are, however, other sorts of non-falsifiable statement which are compatible with mathematics. As we push the possible bounds of human knowledge, we are running into such statements in the form of multiple universe theories and the anthropic principle. Multiple universes are easily and naturally predicted by many mathematical theories, yet it is difficult to see how we could ever have clear evidence for their existence. Nevertheless they clearly make sense, and could exist, and hence our notions of science must expand to encompass these ideas.
The reason such ideas remain science, rather than pseudoscience, is precisely that they are compatible with a fully mathematical theory of the universe. Indeed, the best evidence we are likely ever to have for the multiverse is that is seems to be an inevitable outcome of some extremely compelling mathematical theory that explains many other things that are fully falsifiable in our own universe.
Falsifiability, therefore, retains its central role, in the sense that we can never believe any theory, no matter how mathematically amazing it is, if it doesn't make some predictions that we can actually test. However, it need not have only falsifiable consequences, and we must expand our thinking to include this possibility. Part of this expansion requires that philosophers of science and laymen both must finally come to accept the absolutely central, and completely non-accidental, role that mathematics plays at the deepest levels of physical existence.