I tried to find this in the FAQ, honestly I did, but there is so much stuff to read about responses I just got overwhelmed.

So, this is what happened:

I called a battle challenge with Robb Stark against my opponent. Robb in this case had 5 STR and my opponent defended with a character that had 3 STR so I won. Robb has a response that says "ResponseL: After you win a battle challenge in which Robb Stark participates, choose and kill a character controlled by the losing player." My opponent, who may I note only has 2 characters in play, wants to play an event card that says "Response: After you lose a challenge, kneel one of your Lannister characters to choose and kill a participating character controlled by the losing opponent."

The problem comes in that if I go first with Robb's response, he wont have any characters to kneel to allow him to play that event card. But if for some reason his response gains precedence over mine, then Robb dies and I can't play his response. What happens now??

A couple of things.

First of all, the First Player always has the first opportunity to play a response in a framework action window.

Furthermore, you need to take another look at the concept of moribund in the FAQ. When a character would leave play, it enters a moribund state during which it is still in play for the purposes of passives and responses. Then, at the end of the action window, all moribund characters move to their respective destinations simultaneously (dead pile, discard pile, etc.).

So no matter which of the two responses is triggered first, since all characters are still on the table during all of step 5 (see timing structure), both players get to trigger their responses, and all characters leave the play area after no more responses are played.