This is written in archaic or Classical Japanese style.
信じがたき = 信じがたい "hard to believe". In bungo, い adjectives used attributively (before the noun) ended in き, but ended in し when used predicatively (after the noun). Eg: 高き山 "a high mountain" vs 山は高し "the mountain is high" In MSJ, it would be 高い in both cases, of course.
なれど is the izenkei of the verb なる , "be", plus suffix ど, meaning "although", so this means "although it is"
So your translation is correct.
The second sentence exemplifies a rule that you are in fact familiar with in phrases like ありがとうございます、おはようございます and おめでとうございます : い adjectives have a special form that precedes ござる . This form is made by changing the endings -ai and -oi to long o and the endings -ii and -ui to long u. Thus: あぶない > あぶのうございます、 ひろい > ひろうございます、あたらしい > あたらしゅうございます、わるい > わるうございます and so on.
かたじけない is an い adjective meaning "grateful".
So the second sentence means "I am grateful [for that]"
Examples of this form, apart from a few set expressions such as those cited, are not commonly heard nowadays. A couple that I have come across are すくのうございます "There are not many", from a very aristocratic lady who spoke extremely elegant Japanese, and あぶのうございます "It is dangerous [so don't let your children play on the escalators]" in an announcement over the public address system in a supermarket.