理屈はあなたのおっしゃる通りで、 ”he believes you” の内容を指すことになるので What ではなく、 That になります。そもそも What he believes is ... は、「彼が信じているものは・・・」と言う意味の時に使うので What he believes you is... だとおかしいですね。
That .... is ... と言う構文も実際に使いますが、It is .... that... と同じく少しフォーマルな感じになるのでくだけた会話などではあまり聞かないかもしれませんね。(今の例だと口語では I’m sure he believes you. くらいでしょうか。)
That ... is ... の例として、J. MonroeのState of the Union Address (1823) の一節を挙げておきます。
... there is good cause to belive ... that Greece will become again an independent nation. That she may obtain that rank is the object of our most ardent wishes.
トピ主さんのおっしゃる通り「It is certain that he believes you.」を考えると自然ですよね。「that S+V+O」という形は名詞節と呼ばれ、ひとつの名詞と同様の働きをすると考えてみてはいかがでしょう?そして「what S+V」のwhatにはO(目的語)がすでに含まれている、と考えてみてはいかがですか? とりあえず、皆さんが指摘されているようにこのトピの例分は使われる頻度は非常に低いと思われますが、文法を理解する上では有益なのではないか、と思います。 蛇足かもしれませんがres2のかたの「All (what)...」というやつは「All (that)…」なのでは?()内は文法上関係代名詞として扱われ、allは先行詞ですよね。whatは「先行詞を含む関係代名詞」とされています。よって先行詞を要しません。また、allはwhich,whoの関係代名詞を続けることの出来ない例外的な先行詞として扱われています。よってthatが適切かと思われます。