Have you considered Path to Exile and Utter End? Nothing like exile to get rid of opposing Avacyns.

As for creatures, Bladewing the Risen is handy for getting dragons back. Thundermaw Hellkite and Stormbreath Dragon are good five drops to have, in case Kaalia can't hit the field. Stormbreath is also immune to StP and PtE.

Aurelia, the Warleader is almost an auto-include in a deck that wins with the combat step. Hellkite Charger also grants extra combat steps, but you need seven mana to do so. He also goes infinite with Sword of Feast and Famine (provided you have seven mana, obviously).

Blood Speaker is a handy tutor, along with Rune-Scarred Demon. Archangel of Thune is also fun, nothing like buffing all your creatures, as if they weren't big enough already.

Fervor is a great card in a deck like this. Slap that down, and next turn Kaalia with haste. Phyrexian Arena is also very handy, card draw is always always good to have, and you don't need triple black.

Sorry for the huge wall of text. If you want, feel free to check out my Kaalia deck: There Are No Brakes On The Revenge Train

Hey mate, thanks for the massive input. Some of your suggestions have been in and out of the deck already. For example I tried out Aurelia some time ago and found her just too fragile to keep her in. I'll see if I can fit Fervor in though.

Did you skip Master of Cruelties on purpose?

Hey PlattBonnay! Actually yes, I did. Same is true for Armageddon and such. Kaalia is such a powerhouse on ist own that I'd rather try to keep the deck somewhat beatable for the other players as well. Maybe I'll post a list of stuff i intentionally excluded soon, might be helpful.

Yeah, a list of cards you won't consider or have already tried might be nice.

Yeah, I agree with ThisIsBullshit, toss up the list of cards that you won't consider for the deck.

Although I would suggest helping your friends upgrade their decks so that you don't have to intentionally limit yours.