As someone who has taught thousands of kids, worked management level at a pool with a massive swimming lesson program and spent literally thousands of hours in the pool I'm gonna jump in on this.
First things first: While the pool may have many instructors, it is very very difficult for them to actually change the instructor of a particular class. Not to mention the lesson coordinators will HATE this idea. Instructors build trust with the class from the first moment of the first lesson in a session. So asking them to switch an instructor could very well be detrimental to 8-10 other kids even if its a benefit for yours. Not to mention that often parents will request specific instructors if they have had older kids come through the program or know a teacher they have already had teaches a higher level.
The best thing you can do if you notice that your kid is not responding to a particular instructor is to, as soon as possible, bring it up nicely with the coordinator and ask for your child to be switched (the actual instructors in the pool have no ability to change things and distracting them will put you on the coordinator's bad side very quickly). Do this during your kids lesson so they can observe your child specifically.
Second: If it's already past the time in the session you can do the above (i.e. past the first or second lesson), then consider moving your kid down to level 1. You say that you don't like this solution but it's really not as bad as you think. Most instructors teach either the upper levels or lower levels depending on how they do with age groups and the instructors skill level with swimming. However all instructors that are certified Water Safety Instructors are taught to teach all levels. And while a teacher does spend time with the group, a good one should be spending some one on one time with each child. Often an instructor will notice a kid is slightly above level on their own, but the coordinator can always tell them your child is coming from a higher level class. In these situations the instructor can do extra with your child during one on one time. As a side note for your kid personally, unless your talking about pre-school levels, I as an instructor/coordinator would hardly ever feel comfortable having a 4 year old in a level 3 class.
I would also like to mention for everyone out there: Often teachers are 16 or 17 years old and feel terrible if they don't pass all the kids in their class. However just because your kid passed a specific level does not mean that they are proficient at all the skills taught at a particular level. Every instructor has seen their coordinator or another instructor yelled at cause a kid wasn't passed. Think about when you were 16, would you have felt comfortable failing a kid if you thought it would get you yelled at by a random adult?
Finally: Are your lessons split into summer/winter sessions or have you been in lessons for the last 6 or 7 months straight? The answer makes a huge difference. If it is split and this is the first active swimming your kid has done since the last session, your kid would almost definitely benefit from repeating level 1. In fact if this is the case your kid is probably terrified of the water depths and skills being taught in level 2 and not the instructor at all. If you expect your child to go smoothly from level to level with a split session set up then it is CRITICAL that you observe their class, and in the months in-between sessions you get in with your kid OFTEN and practice those skills. If you don't then you should have 0 expectation of your kid being prepared for the next level up each session even if they did pass their last class. And your doing your kid, others kids and the instructor a huge disservice by moving your child up to the next level.
The very best thing you can do for your kid at the end of each session (besides practicing with them!) is to talk to the instructor, show them your nice, and your not going to yell at them, and then ask for their honest opinion. This will be much more informative then a pass/fail card. Do this twice during a session, half way through and at the end. Again, only do it when they are not in the water, and don't keep them from their next class!