Solution:

We will prove that $N=255$ is the smallest value.

- Let us first construct a tournament with the described properties and 255 participating teams. First arrange 251 Californian teams in the circle and label them by $0,1, \ldots, 250$ in the counter-clockwise direction (0 is Alcatraz). If each team won the games against its first 125 opponents in the counter-clockwise direction and lost against the other opponents, then each team has won exactly 125 games. However, if we look at the tournament with all outcomes the same except for Alcatraz winning the game against the team 250 (instead of losing it), then Alcatraz is the unique Californian champion, and 250 is the unique Californian loser. From now on, let us denote by $L$ that unique Californian loser. $L$ has won 124 and Alcatraz has won 126 games. There remain 249 teams in California, each of which won exactly 125 games. Let us split them into two sets $P$ and $Q$ containing 125 and 124 teams, respectively.

Now we will add the remaining 4 non-Californian teams. Denote them by $A, B, C, D$. They should all win against Alcatraz (then Alcatraz has exactly 126 wins), $A$ and $B$ should beat all teams in $P$ and lose against teams in $Q$. $C$ and $D$ should do exactly the opposite. Now each member of $P$ and $Q$ has 127 wins, each of $A, B$ has 126, while $C$ and $D$ won 125 times. Let us make $A$ win against $L$, then $A$ won 127 times; let us make $L$ win against $B, C, D$. Then $L$ has also 127 victories. If $B$ wins the game against $A$, then it will have 127 victories as well. If $C$ and $D$ win against $A$ and $B$ they will have 127 victories. Now each team except for Alcatraz has 127 victories. (There is still one game remaining - the one between $C$ and $D$, we don't care about that one.)

- Now we will prove that there is no tournament with less than 4 foreign teams. First of all, Alcatraz had to have at least 126 wins; otherwise there will be at most $124 \cdot 250+1$ victories in the Californian subtournament, but the total number of games (and hence victories) is $125 \cdot 251$. Other teams in the tournament had to win at least 127 times. However, in the Californian sub-tournament, there is a team who won in no more than 124 games (otherwise the number of wins would be $\geq 125 \cdot 250+126>250 \cdot 251 / 2$ - a contradiction). Denote one such team by $L$. We immediately conlude that there are at least 3 foreign teams who lost to $L$. Assume that there are only three non-California teams. Except for Alcatraz, each of the Californian teams won in at least two of the games against foreigners which amounts to not less than $250 \cdot 2$ Californian victories. There are $3 \cdot 251$ such matches, so non-Californians could win in at most 253 games against Californians. They played additional 3 games among themselves, so they made at most 256 victories, which is a contradiction to the fact that each of them won at least 127 times. Therefore $N \geq 251+4=255$.