Indeed, Gym Leaders should stick to 4 Pokemon of their type. Rock, Ice, Bug and Fire have it rough, but it's still doable. Being the Bug Leader for a time, I had a good enough team where the main worry of Stealth Rock, Heatran, and the Mega-Zards could be easily mitigated with my wildcards. Brave Bird and the rare Mega Pinsir weren't bad either. It's definitely do-able with Ice and Fire, and to the hardest degree, Rock.
E4 should keep the 3 Pokemon of the type. Like Mr. Y said, having 4 in a team can take away a lot of psynergy, and for Psychic, it's hard to manage a team with only 3 Wildcards. One of them is almost a give, so I really only have 2 to work with. Other types have it a bit easier, besides the ones I'll mention below, but for types weak to 2 forms of priority on average and a lack of priority users outside Ubers (and even in Ubers), it would make teams a lot easier to get through.
In terms of the being able to switch out a Pokemon after each E4, this I disapprove of, as it makes the E4 a bit too easy.
I'm okay with a Continue, but that's it. I don't like the ability of being able to switch halfway through, as one could easily make a team based around 2 E4 members, beat them, then go grab there other team based around the other two members. It makes things even easier than switching out a Pokemon. Just my 2 cents.