The very German Eddie Kessler is played by Anthony Laciura, who is very American. The casting crew was in fact surprised when they learned that Laciura, who had made his entire introduction in a German accent, was actually an Italian-American from the Bronx.
The Italian Gyp Rosetti is played by Italian-American Bobby Cannavale
Fake American: Englishmen Stephen Graham, Anatol Yusef, Jack Huston, Marc Pickering, and Ian Hart as Al Capone, Meyer Lansky, Richard Harrow, young Nucky Thompson, and young Ethan Thompson, respectively. Frederick "Fred" Elliot is played by Scottish Peter McRobbie.
Fake Irish: Scottish Kelly MacDonald and Englishman Charlie Cox as Margaret Rohan Schroeder and Owen Sleater. Also, Scot Tony Curran as Margaret's brother Eamon. Irish-American Nucky Thompson is played by Italian-American Steve Buscemi who is of half-Irish descent.
Also, the French Isabelle Jeunet is played by Swiss actress Anna Katarina.
Washington-born Jeffrey Wright plays Trinidarian gangster Valentin Narcisse.
Terence Winter and Dabney Coleman confirmed that the Commodore's stroke was written in when Coleman was diagnosed with throat cancer, whose treatment made him hard to speak, and as a result sidelined what was first intended to be a large part as the season's Big Bad. This had far reaching consequences in the show's storyline, since it pushed Jimmy to the front of the conspiracy, and made it impossible for Nucky to realistically forgive him. As a result, Jimmy's (and by extension, Angela's) storyline had to be cut earlier than expected, with Gillian and Richard being brought to the front in Season 3 to fill the gap.
Charlie Cox said that they wrote a fight scene with Owen for "A Man, A Plan..." but they didn't shoot it in the end. According to Winter this was because they had to suspend filming when a chunk of plaster from the ceiling of the old baths were they were going to shoot that scene fell off. In the meantime the rest of the episode was put together and, after watching it, they realized that not seeing the fight actually made The Reveal at the end of the episode more powerful.
James Gandolfini was the first choice to play Nucky Thompson. Winter remarks that he had an uncanny resemblance to the actual Nucky, but having just finished his stint as Tony Soprano, he opted out to pursue other roles and to avoid being typecast.
The first casting calls for Season 1 called for the introduction in the season finale of "Declan", Margaret's long estranged brother who was now linked to the IRA. Instead, Season 2 divided this character and introduced separately Margaret's brother Eamonn, a Brooklyn subway-digger with no interest in politics, and Owen, an IRA enforcer completely unrelated to Margaret.
Aleksa Palladino revealed in an interview that one considered plot line for the 3rd season involved Angela and Jimmy moving to NYC, and Angela meeting a female activist that would introduce her to Anarchism.
The first casting calls for Al Capone's brothers Frank and Ralph came out in Season 2, but Domenick Lombardozzi (seen in The Wire and Entourage) was confirmed as Ralph only in Season 4. In Season 2 Al mentions that he is going to Brooklyn to take his brothers and bring them to Chicago.
Shortly after the Season 2 finale there was a very talked about call for (and even leaked auditions of) a new "young", "sexy" recurring gangster character named Bud Matheson that was perhaps too reminiscent of Jimmy. A similar call for a "young", "sexy" college freshman called Michael McHugh came after Season 3. So far, neither seems to have made the cut in the end, though elements of both likely found their way into one-shot character Rowland Smith and Eli's eldest son, Willie.
If Dabney Coleman had not had throat cancer, the Commodore would not have been incapacitated early in Season 2 by a stroke and remained the season's main antagonist. It's likely that the season would end with Jimmy killing the Commodore at the request of Nucky (as Word of God is that he would die in the season in every case), rather than Jimmy doing it on his own volition, and Nucky allowing Jimmy to live if he left AC (since the one to order Nucky's assassination would have been the Commodore and not him).
Two seasons and a good chunk of another were excised because of the show's early cancellation. One can only imagine how Eli and Van Alden would have fared on the Chicago gangster wars, how and why Rothstein was killed in the show, or what part Nucky played in the Castellammarese War.