Fake Nationality: Portuguese actress Maria de Medeiros plays a French character (and, comically, in the Spanish-language dub of Pulp Fiction she is incapable of speaking Portuguese rather than Spanish).
Tarantino originally wanted Jules to have an actual afro, but the wig wrangler got a jheri curl wig by mistake. Jackson thought it was perfect for the character and insisted they keep it.
The scene with Marvin shot in the face was also going to be played out differently. It wasn't until a suggestion from Lamarr to Tarantino that the scene was changed to be what happened in the film.
Urban Legend of Zelda: There's been this popular conception that had been awhile since the film premiered that all clocks in the film are stuck at 4:20. While the events of the film had an Extremely Short Timespan, there's only one scene that ran around 4:20, the pawnshop.
Vincent Vega: Daniel Day-Lewis actively campaigned for the part, but Tarantino turned him down. He initially wanted Michael Madsen to play the goofy hitman, but the latter chose to pursue other project instead (a decision he later regretted). Now just imagine Vincent being played by those two instead of John Travolta...
Jules Winnfield: The quintessential Samuel L. Jackson role, but he almost lost this part to Paul Calderón. He eventually kept it, with Calderón playing Paul (Marsellus's right-hand man) instead.
Ringo: Johnny Depp could have taken Tim Roth's part, but unlike Jules or Vincent it was always a fat chance.
Lance/Jody: According to Courtney Love, she and Kurt Cobain were specifically offered the role. Apparently (and unfortunately), Cobain turned it down.
Jimmie: Tarantino had written the role with Steve Buscemi in mind but Buscemi had to turn it down due to scheduling conflicts. Tarantino himself ended up filling the role and Buscemi was given a cameo appearance as the Buddy Holly waiter at Jack-Rabbit Slims.
Butch was written for Mickey Rourke. Rourke turned the role down, since the script was too "out there" and he hadn't seen Reservoir Dogs yet. He has called the decision to pass as the biggest regret of his career. Tarantino next offered the role to Bruce Willis, who was a long shot, as he was still a big-money, A-list star at that point.