The gemarah (eiruvin 19a) states that Avraham Avinu sits at the entrance to gehinom and doesn't allowed anyone circumcised to enter there. The Ariz'l (Sefer Likkutim, Parsha Vayera) states that the first one that Avraham saved from there was his father Terach. How can this be the case if Terach was never circumcised?
Medrash Shochar Tov 9 says that Terach was born circumcised.
@Gershon's answer is spot on. But just in case not everyone agrees, I will offer another. You state in your comment that there are many ma'amarei chazal which state that Avraham was the first person to circumcise himself. This leads you to the presumption that Terach did not have a bris at all.
However see Rashi on 15:15 from Bereshis Rabbah 30:4 that Terach did Teshuva toward the end of his life. In that case it is very probable that he also had a bris done afterwards. His death was long after Avrahams own Milah. (205[Terach died] - 70[Terach at Avraham birth] = 135).
It has just occurred to me that I am not sure why Terach was in Hell seeing as he had done Teshuva but I suspect that is a contradiction not based on my answer. Perhaps I'l ask it separately.