It's unclear to me based on the question whether this is a defined religious belief (as would be explicitly protected by the first amendment and federal law), or if this is a belief that is not so protected. Jurisdiction (including country of course) would have a lot to say exactly where the line there is.
If this is based on a religious belief, or something that is protected equivalently to one in your jurisdiction, your school is required to provide "reasonable accommodations". That doesn't mean 100% freedom to do literally anything, but it does mean the school has to help out if it's reasonable to do so. In this case, it sounds like it is - it's not all that hard to allow a student to change in another room, after all, or to change before/after the rest of the class.
If it's not a religious belief, or something equivalently protected in your jurisdiction, you may nonetheless be able to achieve the same result from the school simply by asking. In fact, assuming you don't want to go to court over this, odds are you'll end up with about the same level of difficulty.
There are quite a few helpful guides out on the 'net to how to ask a school for a religious accommodation. SoundVision's guide is a good one, for example. It boils down to asking nicely, finding a teacher (or other staff member) who is sympathetic - even if not the directly relevant one - and thus can argue your side of things for you, and then asking several times if necessary. As long as you're polite about it, and asking for a very reasonable accommodation, odds are you'll get it - it's easier to do that than to fight the bad PR they'll get if you go onto facebook, right?
One thing to consider, though, is (as you note above) the fact that no matter what you do, you will be acting differently than your peers, and as a result it is inevitable that some teasing arises. I don't think there's any solution that avoids teasing entirely; it sounds like your solution to that (ignoring the teasing) worked well, though of course that only works for those who can.
The least-likely-to-attract-teasing solution is probably to see if you can accomplish the gym requirement through a sports team, which is not impossible in some schools (and is, in fact, common); it's unclear what your desire in the question to avoid removing the child from class comes from, but if it's simply from the desire to still have good physical education this is probably just as good (or better). Yes, you'll still have some form of the same issue; but teammates are more likely to be sympathetic than classmates, and a coach might be more willing to make accommodations - or you can 'shop' for one that is.
