Tauren Chieftain will introduced on DotA 6.60! Before, IceFrog already mention on an interview about the appearance of Tauren Chieftain on DotA Allstars. But recently, on the release of 6.59, IceFrog confirmed that Tauren Chieftain will be introduced on Dota 6.60.
While we don't know what kind of Tauren Chieftain will be made, there's already several idea about Tauren Chieftain on Suggestion Forums of DotA Allstars. You can check the Marn Thunderhorn The Tauren Chieftain idea from Rindurion or another Tauren Chieftain from bama21.
This is the previous IceFrog interview about Tauren Chieftain and the latest things in Dota.
Update 1 :
IceFrog in his blog revealed that on Dota 6.60 there will be a new mode and chance for a new item aside from the previous talked new hero Tauren Chieftain. Here is the quote from the latest IceFrog posted. It will have at least 1 new hero, many hero remakes (mostly partial remakes not complete revamps like the recent ones), some functional improvements to existing Items, Hero balance changes and a new mode or two. There is a chance that a new Item will make it through to the final version as well.
Update 2 :
There seems to be a lot of confusion going on the net. Various leak websites have people posting under my username to confuse players. I'm not sure why some player think that I would post there, but it seems like many do based on the volume of emails regarding it.
DotA Allstars 6.59b Side Quest Guide and Walkthrough - Tauren Chieftain Secret Boss

When released DotA 6.59, IceFrog already tell us that there will be a side quest on Dota 6.59b. And here it is. If you wondering what kind of quest awaited us, you can check the previous DotA 6.49 quest before trying this one.
Start the quest by finding those 4 totems and take those into top left of the map. Activate 4 of element totems (fire, water, wind and earth) and fight the secret boss! Is the boss too hard, the quest is not yet finish. If you can defeat him, you will have a reward. That's Axe of the Chieftain, it gains 200 strength and Chieftain Strike.
This is map of Totems and Icefrogs included.

Here is Youtube about this quest:
I have strategy to defeat him. Here is the way... You can also find 4 secret frogs that will allow you to destroy the totems (the totem is support Tauren Chieftain with aura). Each 2 located in the left top and right bottom of the trees (search with gem for some time and you'll find them) They CAN be killed by spells, but don't do it. Instead make a hero follow Icefrogs and send icefrogs to the location of the totem. After summoning the Tauren Chieftain, use that frog to destroy the totems, since they grant him INSANE regeneration.