Point 1) The Orcs really need a hero that can keep up with the Wolf Riders and Chariots.
Reason: One of the racial strengths and areas of competitive advantage for the Orcs is their speed. Elves still beat them out with the Assassins and birds and whatnot, but for the combo of speed + POW, Orcs seem to have the edge.
To reinforce this advantage, an Orc Hero that gives other Orcs a moderate buff – but that can critically keep up with Chariots and Wolf Riders Something like:
3 leagues / hour
+4 to orcs (but, perhaps, only in Plains and Desert – a nice counterpoint to the Outcast Warchief)
Point 2) The Outcast Warchief isnt useful enough to see placement in decks.
Consider dropping his gold cost to 100G or so, or adding Mountains (or both!). You could also consider making the buff even more impressive… +8 perhaps? The issue is that its hard to get him into favorable conditions since the Orcs dont normally starts anywhere near Forests or Swamps. Even deploying him with the intention to fight in his favored terrain usually means a delay to get him into position as well as to unite with an army to lead. He needs to get a HUGE buff to even sniff usefulness in a deck.
4 leagues / hour
+8 to all units when in Swamps, Forests, and Mountains
This makes him super useful in limited circumstances.