ANSWER: While Exodus 12:43-49 sounds "unyielding," we must understand it and the New Testament scriptures in context.
In Exodus 12, a mixed multitude had gone out of Egypt with Moshe. YHVH, now has to bring the entire group back toward righteousness. In Exodus 12:43, the command is that no foreigner is to eat the Passover lamb. But Exodus 12:44 provides an expanded guidance that those "in your house" - that is, those whom are bound to you (such as slaves)- must then "do as you do" - and they should be circumcised. Verses 45 and 48 make this even clearer as (45) "neither a traveler nor a hired servant may eat it" and (48) "If a foreigner staying with you wants to observe ADONAI's Pesach, all his males must be circumcised. Then he may take part and observe it; he will be like a citizen of the land. But no uncircumcised person is to eat it."
In these verses, you can see two types of people. First, there is the Isra'eli, who is already obedient and Torah observant; and then there are those who are volunteering to be obedient to YHVH - choosing YHVH over the other "gods" of the mixed multitude. That second group, we are told (Exodus 12:48) are "like a citizen of the land."
The entire Bible is a continuous revelation of YHVH, and at this point in Exodus, we are pretty much seeing only the image of obedience without really being able to understand why. So here in Exodus 12, the commands are pretty much without explanation as to why. In Genesis 17, when YHVH is making His covenant with Avraham, YHVH tells Avraham that the circumcision is a sign, everlasting, and pretty serious!
Much later, in Jeremiah, something new about circumcision is revealed:
Jeremiah 9: 25 "The days are coming," says ADONAI, "when I will punish all those who have been circumcised in their uncircumcision - 26 Egypt, Y'hudah, Edom, the people of 'Amon and Mo'av, and all those living in the desert who cut the edges [of their beard]: "For although all the Goyim are uncircumcised, all the house of Isra'el have uncircumcised hearts."
Here we learn that YHVH is expecting more than the outward, visible, physical circumcision. He is expecting that the circumcision be a sign of your heart; that your obedience be honest and toward seeking righteousness. (See Jeremiah 9:13-14.)
Then, in Acts, Romans, and 1 Corinthians, we have Rav Shaul expanding on this lesson that the physical act of circumcision is not the important factor. It is, instead, the result of one's having come to faith, setting their heart on the Word. Then, the act of circumcision comes to the Gentile only after he has gelled his faith and understanding that to be obedient to YHVH means to abandon the ways of the world. Paul says in Romans 4:12 that blessedness is not due the circumcised, but to those who "fulfill the steps of the faith of our father Avraham in his uncircumcision."
Knowing how important circumcision is as part of the covenant, Paul would have never taught against it. If he was against it, as many like to insist, he would not have made Timothy go through with the physical circumcision (Acts 16:3). Paul desired this one to go forth with him, and therefore, he circumcised him, because of the Jews who all knew that Timothy's father was Greek....
So, let's go back to the two types of people. The Isra'eli (today commonly referred to as the "Jew") who is circumcised at birth has no choice in his circumcision, but still has to choose to be obedient to the Word, otherwise his circumcision is "nothing." Similarly, for the Gentile, he should not be circumcised for the sake of being circumcised (1 Cor 7:18-19). For both, the key is to keep YHVH's commands (but willingly, not by rote or by tradition.) (1 Cor 7:19.)
So concerning your question as to whether or not "non-Jews are supposed to be circumcised," the answer is "yes" - however, but that answer carries with it a caveat. If the non-Jew has decided to obey YHVH, follow His Word, and become obedient to Torah, then that person becomes obligated to obey as many of the commandments as he can, and this includes circumcision. This circumcision, however, should not occur until "the heart is right."
Concerning the attendance of the uncircumcised at Passover:
Certainly in the days of Moshe, since it had not been revealed to the Isra'elis the greater meaning of obedience to Torah (and since the Messiah had not yet come to be the Final Sin Sacrifice, and the participant in Passover was consuming the lamb which had been slain for them), it was a requirement for the attendee to be circumcised prior to the Passover. Today, we: (1) observe the Passover as the "forever" command it is (Exodus 12:1); and (2) commemorate its purpose, which is to remember the exodus, the deliverance, and the celebration of YHVH "passing over" the homes of the Israelites in Egypt. But the observance itself is different for us because our Lamb has already been sacrificed.
Today at Passover, we marry the attributes of the Messiah with the original attributes of the Passover, and our celebration is one of learning and growing closer to YHVH. If an uncircumcised man in attendance is learning and seeking to understand and preparing his heart for "the writing of the Torah" then - according to Paul (Romans 2:24-29) - there is probably nothing wrong with his presence at the Passover meal. If this uncircumcised man is committing himself to letting go of his "old nature" and seeking the unleavened bread of sincerity and truth (1 Cor 5:7-8) then he is sure to reach that point, that epiphany, that wisdom, where he will realize that he can obey YHVH in the fullness YHVH expects, and he will want to observe all the mitzvot he can observe, and he will want to become circumcised.
This man then, will have come to this point righteously, being filled with a deeper understanding, having grown closer to YHVH, rather than "just doing what Torah demands." Afterwards, his NEXT Passover will be fuller, greater, and a more Ruach-filled experience.
By no means should any man become circumcised just to comply with Torah. Rav Shaul taught this clearly. Circumcision comes after Faith as it did for Avraham (Romans 4:12).
While the wise Rabbis may disagree with the idea of the uncircumcised being allowed to partake in the Passover meal, the fact is, the Apostles taught that one is to bring the Gentiles into the fold slowly, by not levying on them ALL the Torah at once, and helping them build and grow in their understanding, observing their growth, and allowing them to change their hearts such that when they reach that "ah-ha!" moment (i.e., when they "get it"), they no longer have to be taught by man, but by the Ruach haKodesh (Holy Spirit). Since the Messiah, the Living Word, was given to all, then the participation in the Passover by a seeking, uncircumcised Gentile is not only permitted, but highly desired.