The other answers have some pretty good tips, but there's one thing I noticed that helps endlessly. Shao Kahn, cheap as he is, is very predictable in one way: he will always do a wakeup attack - i.e. if you knock him down, he will perform a special (or taunt) just as he is getting up. The trick is to get behind him at this point to both avoid his attack and get a free hit of you own.
Raiden is quite well placed to take advantage of this as you can get behind him very quickly by teleporting. Once you've knocked him down once, teleport behind him and perform a simple attack to knock him down again (forward and FK works, if I recall). Rinse, lather, repeat.
Don't get too cocky and go for a combo - he will often gain armour (the white flash of invulnerability) and go to town on your face.
The timing needs some getting used to but it's not too hard. It's cheesy, yes, but he's so infuriating that I personally don't feel bad about exploiting his AI. The hardest part is often knocking him down in the first place, as well as maintaining the rhythm.
I'd tried numerous things before I found this, and it's worked on both Story mode and Ladder matches, with a variety of characters.