Smoke. Once I decided he was going to be my main and I practiced with him all the time it was pretty simple. His Shake ability makes Shao Kahn relatively simple to beat even with low health. Just bait him into using his projectiles and it's all over. Before that I tried with Raiden by spamming his teleport and torpedo.
This is for everyone out there trust me on this one use kitana and use down forward Y or triangle on ps3 and just spam the hell out of it back to back non stop I'm almost got a flawless victory on everyone using this it was super easy!!!