This is a quotation from a fairy tale. A young man was turned into a samurai:
信じがたきことなれど、拙者サムライでござる。かたじけのうござる。
I read the first part as 'Although it is hard to believe, I am a samurai'.
What is the grammatical structure used in the second part? Is the word used 忝い (かたじけな) ?
Is this written in classical Japanese? (It is the き ending of がたい and the use of でござる that made me think that)
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.
