I think the best way to balance is to go the match-up direction. The way that is accomplished is by giving each character definite strengths AND definite weaknesses. The strength would be the focus point (game plan) and the weakness would be the work-around (compromise). This way each match-up is unique and characters/players have to do more improvising based on the opponent and his/her group. The last thing you want to do is create Frankenstein, like how SNK did with Iori in King of Fighters, where he can do everything and the kitchen sink. That's a definite no-no.
Characters can be placed in groups and the proper changes can be applied to them based on the group. For instance:
Pixie
Sonya
Jacqui
Kitana
Cassie
Liu
Kollector
Johnny
Brawler
Jax
Kotal
Shao
Baraka
Kano
Mid-Zone
Frost
Sub-Zero
Kung Lao
Noob
Kabal
Geras
Scorpion
D'Vorah
Long-Zone
Skarlet
Jade
Cetrion
Erron
Shang
Raiden
Remember, this is just an example of groups so don't get @ me. lol!
Pixie - Great up-close, do little damage, but have very good mix-up tools. They have the greatest stay-on-you potential, but have the lowest health. Mid/long-range options are weak.
Brawler - Heavy-handed. They do the most damage. Don't have many mix-up tools, but instead look to capitalize on whiff-punishing/mistakes for counter-hits. Have armor on some of their slower attacks to scare players from just tossing out buttons. Being slower, they have the highest health.
Mid-Zone - Fully control the neutral from mid-screen, but are rather limited everywhere else. Health is average.
Long-Zone - They want to be as far a possible from the opponent. This is because they have the weakest exclusive defensive tools and the 2nd lowest health under Pixies. Reaching them takes patience.
Something like this allows every character to have their ups and downs and isn't based around dealing with a Frankenstein/Swiss Army Knife situation. Players will have a focus point that they can make unique for their own usage, but still have a definite work-around (weakness).
Tweak the characters this way. If you're going to take away a character's current strength, replace it with things are worthwhile based on their group/label.
With this, you have no more S-tiers.