人外で無双してる有名作品では「転生したらスライムだった件」と「オーバーロード」あたりがありますね。
有名作品以外で言えばゾンビになったとかスケルトンだとか熊だとか、けっこうあります。

＞改めて考えてみると、何が起きても苦戦もしないし危機にもならない。
いやいや。逆にそれが面白いんですよ。
読者は「そのシチュエーション」を楽しんでいるので。
えーっと。
従来の物語の楽しみ方は、「主人公はこの難局をどうやって乗り切るのか」という楽しみ方で、おそらくスレ主さんもそのように考えてると思います。
でも、いわゆる異世界で無双してる系の読み物の楽しみ方は、「いかにもな敵役がでてきた。こいつはどうやってボコボコにされるのか」って感じなんですよ。
だから別に苦戦も危機もなくていいし、余裕で敵を倒してもなんも問題なくて、まあ俗っぽい悪意ある言い方をすりゃ「どのようにして主人公がドヤ顔するか」その過程でみじめにやられる敵を見て楽しんでるんです。
なので、逆に、そんな物語に無理して「難局」やら「危機」やらを乗っけてもコンセプトが真逆なので面白くなくなる可能性が出てきちゃいます。

だから「難局をどう乗り越えるのか」を楽しさにしたい場合は主人公の設定をそれほど強くない形にする。
前述した通り「主人公の活躍」を楽しさにしたい場合はこれに特化して無双させる。
そんだけの話です。
第三の回答として、この両取りで「主人公は一般人レベルだが、連れの使い魔が最強クラス」というのもありますね。
主人公メインだと「危機」を書けて、使い魔をメインにすれば「無双」が書ける。
この場合、弱い主人公の存在が希薄になるので、個性的な能力を得ている事が多いと思います。
そんで主人公の存在をアピールしてくことになるので、主人公の能力をメインにした物語展開になると思う。

で。
そうなると、スレ主さんは何が書きたいの、って話になっちゃう。
＞やはり多くの方は、“実際にどこかにいそうな人物”を主人公として求める共感を望みながら、“どんな状況でも乗り越えられるかっこいいヒーロー”然とした主人公への憧れも捨てきれないと思うのです。
「多くの方は」ではなくて、スレ主さんは、ではないかと思う。
そういう主人公像はウケやすいし憧れを持ってる人は事実多いだろうと思う。
けど、「危機」がないと面白くないと考えてて、それを乗り越える人物像を見てみると「どんな状況でも乗り越えられるカッコいいヒーロー像」になると思う。
そういう物語が好きだから、逆算して「危機がないと面白くない」と感じているのではないかな、と。
ようは少年漫画的主人公像ですよね。

すると、イメージに合わないのは「強さ」ではなくて「人外」の部分じゃないでしょうか。
でも「人外」は現状作品の個性なので、これを除外するのは私もありえないと思う。
だから、その「人外」キャラが作者の理想に近づく過程の「強さ」を問題視しているのではないかな、と。

なので、いくつかパターンを考えてみると、
まず「人外」の時点で「強い」という先入観を持ちます。基本的にモンスターは人間より強いためですね。
なので、「人外」なのに「弱い」という組み合わせは意外であって、割と面白いと思う。
最初は弱くて間抜けで足を引っ張るキャラでもいいんじゃないでしょうか。
この点については、スレ主さんは「長期連載されてる漫画の、一番盛り上がってる部分の主人公の強さ」をイメージしちゃってると思う。
漫画「NARUTO」も主人公は序盤、最弱で間抜けで足を引っ張りまくってるキャラですよ。でも頑張ってるって描写が好感を持てたわけで。

次に、「人外」で「強い」の組み合わせは、先入観通りの展開なので、お約束になると思う。この場合はやっぱ無双系が合うかなと思う。
タイトルあげても知らんだろう書籍化作品で言うと、死んだ主人公がスケルトンで復活し、ゾンビに進化したことから人間に戻れるのではと悪戦苦闘する話ってのもあるので、無双一択ってわけじゃないけど、やっぱ「強い」だと危機を作りにくいので「危機・困難」以外の楽しみを作る必要がある。
ちなみに、戦闘メインで考えているような気がするけど、「危機」はなにも戦闘に限った話ではなく、主人公は力は強くても全てにおいてパーフェクトではないので、対人関係などコミュニケーション能力に乏しいなどで「危機」は作れる。
ゾンビの例だと、主人公は人間に戻りたいので人間と敵対はしない、しかし見た目はモンスターなのでコミュニケーションが出来ず、ここで「強さは関係ない危機」を作ることが出来る。
古典レベルにベタな手段だと「恋愛に疎い」とかでヒロインに振り回されるとかも昔はよくありましたね。
「危機」の作り方次第で、ようは無双ものは戦闘面でのみ危機を作りにくい。というだけ。
発想の転換が大事。

ほんでついでに、「弱い主人公」と「強い相棒」で考えると、主人公が人外なので相棒は人間が良い比較対象になれる。
この場合、前述したけど相棒に主人公が守られてる形になるので、主人公には主人公の個性が必要で、そしてコンビで考える以上、二人のパワーバランスが崩れることは二人のコンビの「楽しみ方」も変わってくることになるので、割と書くのが難しいと思う。
逆パターンで「強い主人公」と「弱い相棒」では、これもまあ無双系によくある「規格外の主人公が、強いが人間レベルの相棒に凄い凄いとヨイショされる」という形になる（規格外の無双モノでなくとも）。
この場合、「相棒」サイドで「危機」を書くことが出来るので、まあ、弟子の成長を見守る人外師匠というエピソードが考えられると思う。

以上で、じゃあスレ主さんはどんな話が書きたいの、という事になってしまう。
前述した内容は組み合わせのパターンで書ける物語……というか読者に提供する「楽しみ方」が変わってくるので。
それ次第で、主人公の強さをはじめ諸々が変わってくるんじゃないかなと思います。
基本はヒーロー像を求めてる気がするから、「人間にはまず負けない程度には強い」でいいんじゃないかなと思う。
人間相手には強くヒーロー像を書けて、主人公と同じ「人外」相手になれば戦闘面でも「危機」を書ける。
ただこれは、いいとこ取りしようとした妥協案だと思うので、やはり「どんな楽しみ方を想定しているか」という書きたいモノを今一度考えてみるべきだと思う。