Dairou was set to be in MK:DA, but as a Samurai mercenary hired by Shang Tsung.
Havik was originally going to be Noob Saibot, and then became a new character on his own. Also, he was originally referred to as "Skab."
Due to his resemblance to the famous Street Fighter character, Kobra was named "Ken Masters" during development. Many fans were led to believe that a Street Fighter vs. Mortal Kombat game was in the works. Alas, it was just a placeholder, although Ed Boon has said he would love to do a crossover with Street Fighter at some point.
Kitana was originally set to appear in Deception until the dev team decided to include Mileena instead, giving Mileena a pink version of the costume Kitana was supposed to wear (Kitana is shown in this garb in Ermac's Deception ending).
2-on-2 battles were intended to be implemented here, complete with Tag Team Fatalities. Remnants of this can be seen in Noob-Smoke.
There were concepts for Fatality-esque torture sequences. For example, if a player was knocked off of a stage, they'd miraculously grab on the edge and try to pull themselves up. The opposing player could try to stomp on their hands or kick their face to knock them off, whereas the character in peril would mash buttons to climb back up and could grab their foe and fling them off of the arena. The Cliffhanger mechanic in Dead or Alive 5 has some elements of this idea.
The Nethership stage was originally meant to span more areas of the ship, such as the living quarters.
The BGM for the Onaga's Lair was originally a guitar piece entitled "Dragon Slayer." It was deemed to be a bit unfitting for the atmosphere of the arena, but was included as an unlockable piece of music you can listen to in-game.