I wouldn't sat that Nietzsche supported a "new religion" at all. Although he did care that the values of humanity be 'revaluated' - meaning that we should establish values based on 'health-inducing' premises - and not on something simply 'inherited'. And to revalue our morals, we must look backward to identify where the moral values originated that we now regard as common sense.
For instance, in the preface of On the Genealogy of Morality, he says as much:
"My ideas on the origin of our moral prejudices - for this is the subject of this polemic."
Furthermore, upon excavating things like Judeo-Christian "slave morality," I wouldn't say that he finds religion uniquely a 'fraud' especially because he finds a sense of 'life denying' in not only religion, but the asceticism of science and philosophy as well,
"I was the first to see the real opposition: the degenerating instinct that turns life with subterranean vengefulness (Christianity, the philosophy of Schopenhauer, in a certain sense already the philosophy of Plato, and all of idealism as typical forms) versus a formula for the highest affirmation, born of fullness, of overfulnless, a Yes-saying without reservation, even to suffering, even to guilt, even to everything that is questionable in existence."
- Ecce Homo, Birth of Tragedy, 2
Instead of Nietzsche founding a 'new religion' and have people practice it, I think instead he looked for humankind to overcome the struggle between the two systems outlined above. At that point, they would overcome their own 'human-ness' on their way to 'greatness'.
"Man is a rope, tied between beast and overman — a rope over an abyss a dangerous looking back, a dangerous shuddering and stopping. What is great in man is that he is a bridge and not an end: what can be loved in man is that he is an overture and a going under"
- Thus Spoke Zarathustra: First Part, 4
In that humankind may "overcome" the values we inherit culturally _toward those of strength_ is such a personal endeavor I don't think that Nietzsche would think of this as a 'religion' per se. Especially in that religions have ceremonies, prayers to supreme beings, etc.