Coilfang- Honored with Cenarion Expedition (questing in Zangarmarsh, the Cenarion Post in Hellfire or the Cenarion areas in Blades Edge Mountains)
Auchindoin- Honored with Lower City- quests from around Shat and the ones in Terokkar. You can also turn in feathers from the non-skettis birdmen in the Terokkar forest areas for rep with a bird near the alchemy trainer in Shat. Surprisingly this also includes Mana Tombs, but you'll get Consortium rep for running it.
Tempest Keep- Need Honored with the Sha'tar which you can get by running the dungeons on non-heroic mode and some quests in Shat. Like another poster said, if you want to be able to zone in yourself as well (without using the "teleport in" function from the dungeon finder), you need to do a questline starting in Area 52 in Netherstorm to get the key to enter the Arcatraz-- the other two there don't require one.
Magister's Terrace-- for this one, unlike the others, it doesn't require a specific reputation. You need to pick up the quest on the island of Quel'Danas which you can reach by taking the portal in Shat. There will be one quest asking you to enter on normal mode-- make sure you finish each part of the questline and when you turn it in you will be able to enter heroic mode.
I know you said you just wanted the BC Heroic Keys, but you can also get the Shattered Halls key mold by killing a mob by Black Temple and picking up the item he drops (Primed Key Mold) and doing the questline for that as well.
If you're a higher level and you don't mind running some lowbies through it as well you could also run the regular versions of any of the dungeons in the area-- they will give reputation up until Honored.