So, apparently a lot of people seem to have a lot of problems with this game. Getting the Invincibility achievement can be quite annoying to say the least, but here's my strategy guide/FAQ for Yie Ar Kung-Fu.
First opponent: Buchu
This guy is pretty easy, although he's probably the most random of the lot in terms of being either ridiculously easy or completely destroying you. Your best bet is the middle kick (forward + B), he should go down in a matter of seconds. Usually one of the easiest opponents to get a perfect on.
Second opponent: Star
I find the best strategy is to punch/kick her shurikens, then jump towards her and nail her with one or two punches "on the rebound". She'll dash backwards when you hit the stars (or the stars hit you) and she cannot attack you when in that particular animation. Try and take advantage of that by nabbing her with the punches. Punches are faster than kicks by the way, so they're your best bet.
Third opponent: Nuncha
Jumps towards him (again relying on the dash mechanic) followed by low kicks are the way to go here. He's still very easy, yet not as prone to perfects as Feedle. Just don't stay down for too long as he has range advantage and might nick you with 2-3 attacks.
Fourth opponent: Pole
Easy as pie. Move forward a bit, stay right where you are and spam low kicks. He'll go down in seconds because of your frame advantage. Don't give him time to attack himself, as his range advantage will prove a nuissance.
Fifth opponent: Feedle
Easiest enemy in the game. He'll clone himself and come at you from every direction. Time your attacks well and hit him with a middle kick (forward + B). Keep doing this until he runs out of HP, and the clone(s) on the screen will retreat in shameful defeat.
Sixth opponent: Chain
Staying close is the key. Jump towards him (don't give him space as his chain attack might get pretty annoying) and have at him with all the kicks in your arsenal, mostly low kicks will do the job just fine.
Seventh opponent: Club
One of my pet peeves in this game until I found a fool-proof way of beating him. The key to getting the best of him is the spinning punch (up back + A). Wait at the edge of the screen for him to get closer. When his clubbing animation starts, unleash your fury and he'll get knocked in the head. It may take a few fights to get the timing right, but when you do, he'll be a pushover.
Eighth opponent: Fan
Easy, but annoying if you let her. She'll almost constantly be dashing around, making it very hard to land a hit on her. It's also a plus that she barely attacks herself though. Just jump so you clear all the fans she hurls at you and try and get some low kicks in.
Ninth opponent: Sword
Never lost to this guy. Jump straight up and do a low kick upon landing. It's a game of chance really, but you'll find that the odds are really on your side. Bit annoying to wait for him to come into range, other than that: pushover.
Tenth opponent: Tonfun
This is where the difficulty curve of this game shoots straight up. Tonfun is the only fighter in the game there is no absolute strategy for. Just jump towards him and when he does the dash, have at him with one or two low kicks. After that, immediately repeat. Don't stand around waiting for him to attack, as he will slaughter you in seconds in despite of how good you were doing. Usually, this sneaky bliger is the one to get to me before I can finish my "no-lives-lost" run of this game.
Eleventh opponent: Blues
Two words: star punch. Congratulations if you got to him in the first place, but you're not out of the woods yet. Press down and left on the D-pad and wait for him to come into range. Time your punch correctly and press A. Even if you don't manage to hit him, bail out by jumping to the other side of the screen and moving back. He's a very mean sod indeed and one of only two characters (together with Tonfun) to have a completely random attack pattern. If you stick to hitting once or twice and bailing out, you should however be able to beat him, although I have to admit it took me hours upon hours to finally kill him on my first try (as in: not having lost any lives).
That's about it really. The achievements pretty much speak for themselves, except maybe the "land all punches and kicks" ones. You're better off trying these on Buchu, by doing a lot of jumping around. Remember: there's as many punches/kicks as there are life bar pixels. Mess up once by doing an attack you've already done and you might as well restart the game, as Buchu really is the only opponent it's worth trying on.
Hitting Star's... stars with every attack does not
count towards the achievements, as you have to do damage to the opponent.
My status in this game: 200/200. I'm sure you can do it too