You're tellin' me. Yeah, my buddy and I had the same problem. I actually know of a cheap tactic that'll work with Scorpion, but I don't know about Sub-Zero. I gotta give all the credit to Malitor, though, since I used his idea and elaborated on it.
Anyway, with Scorpion, if you have his last teleport punch (the flaming one), you can keep running toward Kintaro (or anyone else) and doing that. If you hit it just right, you'll make them burst into flames and connect with the punch. What I added to that, though, is the final X, X, B combo you can purchase which actually does a ton of damage. Even if the first two hits don't connect, that last one will usually fry 'em good.
Against Kahn, I'd basically do the same thing, but I wouldn't normally run up to Kahn. Instead, I'd just do the teleport punch when I knew I could nail him (like in the middle of one of his attacks), keep running around and dodging him, throwing the head when I had the chance, and using that X, X, B combo whenever he taunted me, had his back turned or was incapacitated somehow.
So basically, I just kept doing the teleport punch and then hitting that X, X, B combo and getting the hell out of the way. I've only tried this in single player mode, but by the time I'd "perfected" that strategy (it did take me 3 or 4 tries), I ended up completely wasting all the bosses. I actually beat the game with most of my life still intact.
Hopefully that'll actually work in ko-op.