Caius and Noel were the last of a line of guardians charged by the goddess/fal'Cie Etro to protect the seer (Yuel). As tools of Etro, guardians were l'Cie, and Caius became a l'Cie by defeating the previous guardian. As a l'Cie, he had the same types of powers and restrictions all l'Cie have—for example, the ability to summon an eidolon (Bahamut) and the inability to abandon his mission—which is why people considered him to be a potential l'Cie.
As to why everyone said he was immortal: it's because he was, in fact, immortal. As described by the Final Fantasy Wikia, his immortality was a gift from Etro for his dedication to protecting Yuel:
Etro was moved by Caius's dedication to the seeress and freed Caius from his fate as a l'Cie and infused her heart, the Heart of Chaos, into his body, making him immortal so he could protect every incarnation of Yeul until the end of time. Although given as an act of benevolence, Caius would eventually see his immortality as a curse due to the madness he would have to endure.
By Caius forcing Noel's hand in destroying the Heart of Chaos, Noel in effect "killed" Etro, apparently allowing Caius to himself be killed.1
However, in the secret ending, he's still alive in the Void Beyond.
Note 1: It's not explained clearly in game why Caius couldn't just commit suicide, but given Caius's belief that only Noel could do it by taking his place as guardian of Yeul, it seems that there must always be one guardian. Since Noel refused to become a guardian by killing Caius, Caius couldn't give up his mission to protect Yeul by killing himself.