would have doneとは？？

こんにちわ。

ここでの、would have done～は仮定法です。
つまり、彼がそういうことをする、と仮定した場合、それはhard to believe、信じがたい、ということで、彼はそんなことする訳ない、という意味合いです。
まだ”そんな事”をしてないけど、「彼がそんなことをするなんて（仮定した場合、それは）信じられない」

つまり、実際に彼は”そんな事”をまだしてはいない、けど、するということは信じられない、という事です。

例にあげられた過去形の文～he did such a thing、にすると、
「彼がそんなことを”した”なんて信じられない」と、実際に彼が”そんな事”を行った、そしてそれは信じがたい！！という意味になってしまいます。

would have done は仮定法過去完了といって、過去のことをいう場合に使う言い方だと思います。

こちらをご覧ください。
http://www.englishcafe.jp/english/day48.html

質問文の場合ですが、「信じられない」といっているのは現在で、「彼がそんなことをしたなんて」と彼が過去にとんでもないことか何かをしでかしたということが信じられない、と言っているのだと思います。