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).
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.