In The Big Lebowski, John Turturro is topped billed but doesn’t appear anywhere near Julianna Moore.
In fact, he doesn’t get a very big part to play at all come to think about it.
Pretty much every animated film records the actors’ voice parts separately.
In Shrek, Mike Myers and Eddie Murphy didn’t record together, nor did Myers and Cameron Diaz.
In fact, for the love scene at the end of the movie Mike Myers acted opposite his wife to get the necessary “vibe”.
Heywood Floyd and Dave Bowman never appear together in 2001: A Space Odyssey.
No, they had a scene at the beginning of the film then at the end where Brad saves both of them from the hitman.
Bat 21, w/ Gene Hackman and Danny Glover.
Vietnam story, Hackman is shot down in unfriendly territory. Glover is a pilot of a light recce aircraft, who only speaks to Hackman over the radio for most of the movie.
But Glover’s character steals a helicopter (his CO’s) and goes and gets Hackman’s character right before the big airstrike. The Helo takes fire and goes down, and the two limp out of the bomb zone arm-in-arm.
The IMDb entry for The Taking of Pelham One Two Three gives top billing for Walter Matthau and Robert Shaw. I don’t remember them on screen together.
There’s the scene where Matthau corners Shaw (Mr. Blue). Shaw ask Matthau something of to the effect if, “Do you still execute people in ths state?”, and when Matthau responds negatively, Shaw electrocutes himself on the third rail.
I didn’t realize anyone still remembered this film. It’s basically the the template for Die Hard, except in a New York City subway car instead of a Century City high rise, and with Matthau standing in the Bruce Willis role, albeit keeping his shoes on and with fewer explosions.
“What the hell did they expect for their lousy 35 cents - to live forever?”
Stranger
You’re right, they don’t meet. I believe they do talk to each other on the phone.
In the movie Innerspace Dennis Quaid and Martin Short interact throughout the entire movie but I think only have a couple of scenes together at the end.
All of Me with Steve Martin and Lily Tomlin is similar.
INNERSPACE almost. Although they are in many scenes together, I don’t think Dennis Quaid and Martin Short are in the same shot together, until the very end of the movie. For anyone who didn’t see the movie, Dennis Quaid was in a space type capsule floating around inside Martin Short, Fantastic Voyage style.
Superman - I don’t think that Marlon Brando and Christopher Reeve were onscreen at the same time.
(There was a scene with a hologram of Jor-El talking to Clark Kent, but I think he was still played by Jeff East at that point. Reeve took over in the next scene.)
Aw, hell. I forgot that.
I shouldn’t comment on movies I haven’t seen in their entirety in 25 years.
Also partial inspiration for Reservoir dogs.
It’s a great film, and I often find myself humming the kick-ass, typical-70s, saxophone-heavy opening/closing theme.
[When a couple of friends of mine were getting ready for their first-ever trip to New York, I invited them over to dinner and gave them some ideas of things to see off the standard “tourist track”. I also lent them my NYC subway map, and explained how the system worked – expresses and locals and such – and which areas to avoid after hours. After dinner, we watched the two DVDs that I’d rented for the occasion: The Taking of Pelham One Two Three and The Warriors. 
]
Just the Mr. <color> gag. “Why can’t I be Mr. Purple?” – Mr. Pink
Stranger
There are two “Marx Brothers” films that fit the bill:
Love Happy - This was originially a Harpo film (he had a lot of sight gags he wanted to do), then Chico needed money so he got in. The financial people would only finance the film if Groucho (then a star on TV) was also in the movie. He didn’t want to be, and agreed to come in and film a kind of narrator role only because Chico needed money, which invariably involved mobsters. (I think this is the time he bought his daughter a Doberman to keep her safe in case she was around when everything fell apart.) The resulting mess (it really is awful) was billed as a “Marx Brothers Movie.” Harpo and Chico have scenes together, but Groucho never has any scenes with either of them, or anyone else for that matter (except Marilyn Monroe, but that makes sense, right?).
The Story of Mankind - This isn’t quite the same. It wasn’t conceived or filmed as a Marx Brothers Movie. It is kind of one of those All Star Cast things. The Marx Brothers are listed as one set of stars (three stars? a star?), but they were filmed separately, and their cameos are totally unrelated. (It might not count as they aren’t top billed, but I vaguely think the billing was in alphabetical order so it’s arguable.)
I was just reading a review of Dog Day Afternoon that pointed out that Al Pacino and Chris Sarandon were never in the same scene together despite the fact that their characters were lovers. The closest they got was sharing a telephone call.
Good one, made even more valid by the fact that Brando and Gene Hackman actually got top billing in that one.
James Garner and Gena Rowlands had all their scenes together in The Notebook. As they were playing the older versions of Rachel McAdams’s and Ryan Gosling’s characters, the first two had no scenes with the latter two.
Saruman didn’t meet any of the hobbits did he?
Edit; Apollo 13, did Kevin Bacon meet the other astronaut who couldn’t make it?