Russia shares a tiny bit of border with Norway. Even if Finland, Sweden and the Baltic states don't want to cooperate, as long as Russia and Moscow agree, the plane could simply take a detour through the far north.
If he would be safe in Noway I think the transportation issue is easy solvable. Wonder if the US would feel like they could kidnap him from the streets, and maybe Norway would promise to look the other way.
The plane would not have to go over international waters and/or other countries, but usually do.
A team of Marines showing up is not very likely; while most Norwegians don't care too much about Edward Snowden (Edward who?), soldiers of a foreign power executing an operation on Norwegian soil would create an outrage that would definitely topple our government. For starters.
I really can't see our (US-friendly) government allowing such an operation, knowing full well it will make them look terribly bad and in all likelihood cost them their jobs AND their reputation.
And the US deploying Marines in Norway without the government's explicit consent? That is called an invasion, and not likely to go down well, either.
But there's no international waters between Moscow and Oslo. The Baltic isn't that big, and even if there is a patch of international waters (which I strongly doubt), it'd be easily avoided.