According to Wikipedia (yes I am linking directly to it and not a source, sorry to all of my teachers.) it seems that the magazines were distributed by news stands in many major USA cities, you did not need to go to the Embassy. But it also go on to note that this was because of an inter-governmental agreement which muddies the water. E.g. "Was it because of the agreement or because of the constitution and we just _said_ it was because of the agreement."
So whatever the exact legal situation was the time, a free speech utopia where even enemies of the US had free reign did not exist. De-facto free speech was significantly more restricted on this topic.
In that particular case, it was a result of an agreement with the Soviet government that allowed us to publish Amerika magazine in the USSR.