It's very odd that you want to keep it consistent to canon, but work with a completely anachronistic variation of the Blackrock Clan.
There's no way to properly insert the Tauren without either allowing artistic liscence, or simply ignore the lore implications altogether as a part of suspension of disbelief. There's no middle ground when you're trying to tell a story in Lordaeron in a time and place where Tauren simply never existed.
I agree with others, simply replace Tauren units with Ogres. Chieftain -> Ogre Lord, Tauren -> Ogre, Spirit Walker -> Ogre Mage. Keep the units the same, just swap the art and voices.
Otherwise, you're free to make your own lore up for whatever rogue Tauren faction travelling to Lordaeron that joins the Blackrocks and convinces them not to serve the Legion. I mean, if we have Highmountains and Yaungols and Taunka all over the world and we have Mr. Smite in Deadmines, we can probably have Tauren in Lordaeron somehow. But honestly, the Blackrock Clan was always identified as the Warcraft 2 Horde, not Thrall's new Horde.