Uhura was originally supposed to be named Sulu. Eventually the name was re-used for George Takei's character.
In Roddenberry's pitch for the Original Series, Spock was described as "half-Martian" rather than half-Vulcan. Presumably, if this little detail had remained unchanged, a sentient Martian species would have become become part of the Trek verse. Spock was also originally planned to have red skin (which would have meant extra hours in make-up for Nimoy), but just before production started it was discovered that the makeup would make him look black on a black-and-white TV (which many people had at the time), and it was feared that this would cause controversy. As the later fallout involving Uhura's introduction showed, they were probably right.
In the original plans for the series the warp drive didn't counteract Time Dilation. (Which may be why we never saw present-day Earth in the series). This is where the concept of stardates originally came from; which shows that the creators didn't fully understand the concept: special relativity means there is no universal time!
The entire series could have been very different if the network executives hadn't declined the first pilot. Jeffrey Hunter was originally cast in the role of Captain Christopher Pike, who would famously be replaced by Capt. James T. Kirk, played by William Shatner. Pike was meant to stay on as the series lead character, but Hunter was unavailable to film the second pilot. Rather than recast the role, they created a new character.
This really is a question for the ages. One has to remember the enormous impact Star Trek has had, not just on entertainment, but on our culture in general. Would a darker, edgier, more cerebral show with a serious, brooding Captain who sometimes had periods of self-doubt be as popular as Star Trek turned out to be? Would it fix itself in our mindset? What influence would it have? There is no way of knowing, but it's possible our world would be quite different had the original pilot been approved.
When Hunter couldn't return but before Shatner signed on, the producers spoke to both Jack Lord and Lloyd Bridges about playing Kirk. Bridges immediately turned it down because he didn't like the thought of being on a sci-fi show, but Lord was interested, provided they gave him way more creative control than they were comfortable with. Negotiations fell through and their third choice, Shatner, was selected.
Funnily enough, Roddenberry originally offered Deforest Kelley the role of Spock.
If you think that's odd, imagine what could have been if Leonard Nimoy had decided not to return for the second season, which he seriously was considering. Had he opted out, producers were looking at an actor named Laurence Montaigne or Mark Lenard to replace him. Montaigne was later given the role of Spock's romantic rival, Stonn, while Lenard, who had already played the first Romulan on the series, would go on to his far more famous role, Spock's father, Sarek. Imagine that; Spock was almost his own father.
James Doohan had tried several different accents as Scotty before settling on his now-infamous Scottish accent.
Chekov was originally planned to be a British character. Supposedly Roddenberry changed it after having a letter from the Soviet Union which praised the show's message, but criticized the lack of a prominent Russian character, although this may be an apocryphal story as American programming wasn't even airing in the U.S.S.R. at that time.
Scriptwriter Norman Spinrad originally envisioned Robert Ryan as playing Matt Decker in "The Doomsday Machine". Ryan was unavailable, so William Windom was cast instead.
An episode was written for Milton Berle to guest star in an episode titled "He Walked Among Us." Berle would have played a sociologist playing God in a primitive society. Berle was a fan of the series and wanted to show his dramatic acting range. But Norman Spinrad's script was rewritten by Gene L. Coon into a comedy. Spinrad was so angry that he wanted the episode scrapped. Roddenberry agreed to bin the episode after reading the script.
Nichelle Nichols almost quit the show after the first season wrapped, going so far as to give Gene Roddenberry her resignation letter, because she was offered a part in a play that was Broadway-bounded. Roddenberry asked her to think about it over the weekend, during which Nichols had a chance encounter with Big Name Fan Dr. Martin Luther King, who convinced her just how important it was for people to see a black performer in such a respectable role at that time (not to mention a black woman in a role that wasn't specifically designed for someone who was black or female, let alone both). For obvious reasons, Nichols didn't argue and the rest is history.
Roddenberry promised Nimoy that if the Spock character creeped out too many viewers, he would have plastic surgery and make the ears look normal. Of course, Spock instantly became the most popular character of the series and the ears stayed.
An episode exploring McCoy's Backstory was planned and shelved at least twice. One of the main points (that he joined Starfleet as an established MD after a nasty divorce) finally saw the light of day in the 2009 movie.
McCoy was supposed to have an estranged daughter named Joanna, who is mentioned in the Universe Bible for the Trek series. In the third season, an episode was written which introduced her, but it eventually mutated into the infamous hippie episode "The Way To Eden", with Joanna being replaced by Chekov's old flame, Irina Galliulin. Ultimately, she never appeared in the series, only being mentioned (non-canonically) in Star Trek: The Animated Series. And, of course, she has made many appearances in the expanded universe. But technically she still does not canonically exist.
Most episodes revolve around Kirk, Spock and/or McCoy. Producers often proclaimed intentions to feature stories focusing on the supporting characters. While Scotty achieved greater prominence in some episodes as the show went on, promised episodes centering around Sulu, Chekov or Uhura never materialized.
"The Naked Time" and "Tomorrow Is Yesterday" were originally conceived as a two-part story, which is why the former ends with an out-of-the-blue time-travel incident that leads nowhere and the latter begins with the Enterprise already back in time due to (in the aired episode) an unrelated time-travel incident.
Harlan Ellison's original script of "The City on the Edge of Forever" was heavily rewritten, mostly due to cost. The aired version was almost entirely written by Star Trek story editor D. C. Fontana, who is uncredited. Ellison was not pleased. Notable differences include:
Instead of McCoy, history is changed by a random drug-dealing crew member. (Gene Roddenberry would later erroneously claim the script featured Scotty dealing drugs.) Unlike McCoy, this character is a proper villain who murders a Red Shirt who tries to report him. At the end of the episode, the drug-dealing crew member escapes into time again, only to be caught in a star the moment it goes supernova. Time replays itself continuously afterwards, forcing him to relive the supernova again and again as his eternal punishment.
Yeoman Rand is the only named character to beam down to the planet with Kirk and Spock. In the final episode, Scotty and Uhura share this role. (Rand had suffered from Chuck Cunningham Syndrome by the time the episode was filmed.)
Instead of simply disappearing, the Enterprise is replaced by a ship of Space Pirates. This part was apparently forced on Ellison by Executive Meddling, only to be deleted from the final version anyway. A similar concept was later used in the episode "Mirror, Mirror".
The Guardians of Forever (note the plural) are nine-foot-tall aliens who guard the Time Vortex of the Ancients. Thus, the Guardian of Forever in the final episode is not just a Composite Character of the two aliens, but also of the vortex itself.
Kirk and Spock are taken in by a janitor and first encounter Edith Keeler when she makes her speech. Kirk and Spock recognize her as their focal point in time immediately and spy on her for awhile before making contact.
Kirk does let Edith fall down the stairs, realizing in time that she is meant to die. Edith survives the fall, but is confused by Kirk's behavior and he ends up feeling guilty. When the climax rolls around, Kirk is frozen with indecision over whether to let Edith die, forcing Spock to step in and restore history. (This seems to be the change Ellison is most upset about, feeling that his version makes Kirk flawed and human.) The general consensus from those who've read it is that it would make a great standalone story, but as an episode of Star Trek it just feels wrong
An early draft of "Who Mourns for Adonais?" reveals at the end that Carolyn Palamas is pregnant, presumably by Apollo. This bit survived into the Blish adaptation, complete with McCoy complaining his medical training didn't cover being pediatrician for a god, but was cut by the time the script was shot for obvious '60s-TV-values reasons. It also survived into the Star Trek Novel Verse, where Palamas' part-deity great-grandson is a main character in Star Trek: New Frontier.
Harry Mudd was planned to make a third appearance on the show in an episode titled "Deep Mudd". In it, Mudd—left trapped on the android's planet by Kirk and crew at the end of "I, Mudd"—would've escaped with the help of some Space Pirates that he bribed with a cache of advanced weapons he had discovered on the planet. By the time Enterprise caught up to him, he would've lost control of both the weapons and the pirates, once again needing to be bailed out. The episode got scrapped due to Roger C. Carmel being unavailable at the time.
The Klingon Koloth from the episode "The Trouble With Tribbles" was envisioned as a recurring character and arch-nemesis of Kirk's; this was established at their meeting at the beginning of the episode ("My dear Captain Kirk" / "My dear Captain Koloth"). William Campbell, the actor who played Koloth, once said in an interview that he would have played Koloth as Kirk's equal and opposite in the Klingon empire, and someone who respected his adversary, to the point where he would save Kirk's life from other enemies on occasion, declaring that nobody could kill Kirk but him. Alas, Campbell was unavailable when Klingons were next cast, so we got Kang ("Day of the Dove") instead. When the character shows up again in "Trials and Tribble-ations" (DS9), his friend Dax mentions that Koloth's greatest regret was never getting to meet Kirk in battle.
In the outline for "A Private Little War", the arms dealer was Kirk's old foe, Kor (from "Errand of Mercy"). It would have been Kor's second appearance in the Kirk timeline, barring The Animated Series. The producers differed on this point, saying it made no sense that Kor would just be hanging around on a random M-class planet.
The penultimate episode of Season 3 was originally scheduled to have been "The Joy Machine", which would have been written by Theodore Sturgeon and Meyer Dolinsky, and directed by William Shatner (who would thus have beaten Leonard Nimoy to the first Directed by Cast Member credit by 15 years). It centred around a planet used as a dumping ground for mentally-ill people kept placid by the titular machine, which ends up running amok and affecting the Enterprise crew, with Scotty also getting a love story. The story was cancelled when the network cut the season short at "Turnabout Intruder."
The planned Season 3 finale was "The Godhead", which was going to be written and directed by John Meredyth Lucas. This one featured an alien who planned to absorb the entire universe into its mind, with Kirk being forced to put the moves on the the only other (female, naturally) surviving member of his species. As with the aforementioned story, it was canned when the third season was shortened.
Had a fourth season been made, Season 3 story editor Arthur Singer would have been replaced by Margaret Armen, who had just come off writing two of the third season's most popular (well, at the time, anyway) episodes, "The Paradise Syndrome" and "The Cloud Minders". Odds are at least one or more of the regular cast would have been jettisoned for cost-saving reasons, too.