An interesting combo with Cave Troll and Dawn of Destiny is when you play a couple big allies like Great Bear, Energetic Dragon, or Hideous Ogre, along with Cave Troll; Cave Troll registers those cards as costing less than 4, since Dawn of Destiny decreases their cost. This means you can play cards that cost more than 4 without all your Cave Trolls returning to your bench. Cave Troll also has great synergy with Gifts From Above, since playing Cave Troll from the bench counts as playing a card.
Cave Troll does not fear combat, either. When he has taken damage, just play something that costs 4 or more to return him to the bench and play him again so that he is healed fully. He is also the only ally that can block twice, unassisted, during combat. Cave Troll is in play and blocks against an ally, then you play a card that costs 4 or more from your bench. Cave Troll is returned to the bench with its ability and you can play Cave Troll from the bench and block again. Cave Troll survives Killer Wave and other cards like it that cost 4 or more, which means Cave Troll can continue to run rampant. It's especially great when you are the one playing Killer Wave, because all your copies of Cave Troll survive.
Strong against: both control and aggro decks.