そもそもの話として、東方Project内において「〝ありとあらゆる全ての〟神・妖の類は人間からの信仰により存在している」と語られてはいないことに留意が必要です。
結論から言えば、人間の信仰に関係なく存在する神・妖、あるいはその他のオカルトはありうると捉えた方が自然かと思います。
まず、おっしゃる通り「神々が大地を作った」「伊弉諾が日本を作った」と記述がある他、へカーティアの存在からギリシャ神話の背景（または、それに近しい神話形態）が東方Project内には存在しているとして良いでしょう。そうした場合、人間の信仰を第一として神が生まれる構図は矛盾しています。自然に考えれば、人の信仰に関係なく神様は存在していることになるかと思います。
あるいは「神話という物語」を鵜呑みにしたらそうなるかもしれないが、それはあくまで「人間の語った話」なのだから、それさえもが作り話・人間の信仰であると考えるかもしれません。確かにそれは面白い考え方なのですが、地の文にて創造神話が示唆されたり、神話上のキャラクターが登場している以上は、その論に力を感じることができていません。
また、「神、妖怪、その他のオカルトな存在」に明確な境界はないという点に目を向けてみたいと思います。
例えば、里乃と舞はomakeテキストにおいて「隠岐奈の魔力により人間では無くなっている。」と記述されています。これを人間の信仰による妖怪化と捉えるのは些か不自然でしょう。他にも一輪が人間から妖怪化したケースなど、特定の信仰・想い・謂れ・概念に関係なく妖が生まれたケースは複数あります。
さらに視点を広げてみれば、同じように信仰や謂れに関係がないと思われる固有の能力は（蓮子の眼、菫子の超能力など）妖怪化のケースより多数存在します。信仰や謂れに関係がなさそうなオカルトな能力が存在するのに、神や妖怪に限っては信仰限定の存在である……とするのは、やはり些か不自然かと思います。
神と妖、そして人間の境界はあやふやで、そこに付随するオカルトな要素に必ずしも人間の信仰が関わっていない。作中要素のみを拾うのであれば、そう考えるのが自然かなと捉えています。
もちろん、それらをひっくるめて「全て人間の信仰や想像が生み出したものだ」と論ずるのは面白いことだと思います。しかし、個人的には作中にそのような強い示唆があるとは思えておらず、結論としては信仰によらない神や妖も存在するだろうと考えています。