The first Mishna in the eighth perek, see 70a) taught that an arel – someone who is not circumcised – cannot eat teruma. The Gemara derived this law from a similar one forbidding an arel from partaking in the korban Pesah (see Shemot 12:48). There are other people who also cannot participate in the Pesah sacrifice – specifically non-Jews, who are listed as ben-neikhar (an “alien,” as in Shemot 12:43), and toshav ve-sakhir (“a sojourner and a hired servant,” see Shemot 12:45).
The Gemara understands the ben-neikhar to be a Jew who has become an apostate.
One suggestion regarding the definition of toshav ve-sakhir is that these are the cases of aravi mahul ve-givoni mahul – Arabs or Gibeonites who had a tradition of circumcision, but who nonetheless could not participate in the Passover sacrifice.
The rishonim question why we need to be taught that a non-Jew cannot participate in the korban Pesah once we know that a Jewish apostate cannot do so. The Ramban and Rashba argue that someone who rejects the Jewish faith could very well be considered worse than a non-Jew. The Behag suggests that the case of an aravi mahul is one where the non-Jew had begun the process of conversion to Judaism and had already accepted mitzvot and gone to the mikvah, but had not yet completed his brit. This halakha is teaching that he must complete the conversion, even though he already has undergone a circumcision of sorts.
It appears that the case of the givoni mahul is not a reference to the Gibeonites mentioned in Sefer Yehoshua (see chapter 9), but rather to another nation. Some manuscripts refer to them as gavnuni mahul, and Rabbeinu Hananel explains that they were a nation who lived in the mountains – some say on the east bank of the Jordan, others suggest that they were in an area called Gubia, south of the Caucasus. In any case, as Rashi explains, they were a nation that had a tradition of circumcision, even in the times of the Talmud.