A few weeks ago, Fringe reminded us Back To The Future originally starred Eric Stoltz, before the movie started over with Michael J. Fox. But plenty of other SF/fantasy movies filmed a bunch of scenes, then started over from scratch.
Movies that replaced a star after filming had already started:
Demolition Man originally featured Lori Petty as Lenina Huxley — but after a few days of filming, she was canned and replaced with Sandra Bullock. Some fans claim to have seen behind-the-scenes footage of Petty in this movie, including an alternate ending where she kisses Stallone's character. But none of this footage seems to be available.
Lord Of The Rings shot a few days' work with Stuart Townsend playing Aragorn, then replaced him with Viggo Mortensen. Townsend told Entertainment Weekly:
I finally read an article where the filmmakers said, "We were totally wrong about Stuart and we accept that it was our fault," which was so nice because I did get shafted up the a—. I was there rehearsing and training for two months, then was fired the day before filming began. After that I was told they wouldn't pay me because I was in breach of contract due to not having worked long enough. I had been having a rough time with them, so I was almost relieved to be leaving until they told me I wouldn't be paid. I have no good feelings for those people in charge, I really don't. The director [Peter Jackson] wanted me and then apparently thought better of it because he really wanted someone 20 years older than me and completely different.
The Matrix: Reloaded originally featured singer Aaliyah as Zee, but she died in a plane crash during filming. So they replaced her with Nona Gaye, daughter of Marvin Gaye. One of Aaliyah's original scenes from the film was on Youtube and various other sites at one point, but appears to have been taken down.
The Imaginarium Of Doctor Parnassus famously starred Heath Ledger, who died during filming. But most of the scenes that Ledger shot appear to be in the final version of the film — the actors who replaced him (Johnny Depp, Colin Farrell and Jude Law) only play him when he's on the other side of Dr. Parnassus' magic mirror, in sequences that had yet to be filmed.
There are also some famous examples of this on television — the original Buffy The Vampire Slayer pilot featured Riff Regan as Willow instead of Allyson Hannigan. Firefly's Inara was originally played by Rebecca Gayheart instead of Morena Baccarin. (Joss Whedon had an inkling he might recast this role, so he shot all of Inara's scenes with just her in the frame, so she'd be easy to replace without reshooting other characters' lines.) A Twilight Zone episode called "The Mighty Casey" starred Paul Douglas, who died during filming and was replaced by Jack Warden. And the Star Trek: The Next Generation episode "The Most Toys" originally featured David Rappaport as the greedy collector who wants to own Data — but Rappaport committed suicide before completing filming, and the part had to be refilmed by Saul Rubinek. And as a few people have pointed out in comments, Geneviève Bujold was originally set to play Captain Janeway on Star Trek: Voyager, but was replaced with Kate Mulgrew after a few days' filming. (I'd meant to include that example, but somehow forgot.)
Movies that replaced the director and had to make drastic changes:
Enemy Mine was filmed almost in its entirety on location in Iceland, with director Richard Loncraine. And then Loncraine was fired, and the movie was filmed all over again, from scratch, in a studio, with director Wolfgang Petersen. We interviewed star Dennis Quaid a while back, and he said this would have been a very different version of the movie, due to the gritty location shooting. But even Quaid's never seen this version, which is crying out to be a DVD extra.
Jaws 2 was originally supposed to be directed by John D. Hancock, whose wife wrote the film's script. Hancock reportedly wanted the film to focus more on human characters and less on the shark. The studio fired Hancock and, according to the DVD documentary, approached Spielberg to come back and direct the sequel — which Spielberg would only do if he could scrap everything that had been filmed so far. Instead, the producers hired director Jeannot Szwarc, who revamped much of the movie.
Damien: The Omen II director Mike Hodges fled the set a few weeks into filming — after an incident where the producer pulled a gun out of his bag and placed it on the table during discussions. "And then we just looked at each other for a bit," Hodges said during an interview. Hodges was replaced with Don Taylor, but it doesn't sound like Hodges' scenes were scrapped — so this is an edge case.
Exorcist: Dominion was originally directed by Auto Focus director and Taxi Driver writer Paul Schrader, who was fired and replaced with Renny Harlin. But Schrader's very different cut of the film actually did get a limited cinema release under the title Dominion: Prequel To The Exorcist.
Superman II is notorious for the fact that director Richard Donner was fired during filming and replaced with Richard Lester. Lester reshot a large chunk of the film, but Donner's original footage remained intact, allowing him to reissue his own version, the Donner Cut, in 2006. According to Wikipedia, Donner would have received a director credit on this film if at least 51 percent of the footage had been shot by him, so Lester had to reshoot large chunks of the film to avoid sharing director credit. The Lester cut also removes all of Marlon Brando's scenes (so the producers would avoid having to pay him.)
Additional reporting by Mary Ratliff. Thanks to Marc Bernardin, Lisa Eastman, Michael O'Brien, and Jerry Conner.