Both expressions are very common and universally understood in mathematical English written by native speakers -- which means that that, as a practical matter they are both right. And if a dictionary claims that "denote" can't be used in this way, that is the dictionary's fault.
Your assumption that (2) requires that the symbol has already been mentioned does not match how these phrasings are used in practice. Indeed, a sentence such as (2) would commonly be found in an early section of a paper entitled "mathematical preliminaries" or something like that, where the author briefly summarizes the symbolism that he's going to use in the rest of the paper.
As a writer your wording would probably sound most natural if you use the bare statement of fact "N denotes ..." for notation that already exists, such that the sentence just reminds the reader what is already true, whereas "We denote ..." or "Let N mean ..." and so forth are for definitions that are part of the original content of what you're writing, and therefore are new to the reader.
However, as a reader you shouldn't try to extract any meaning at all from the difference between these phrasings. The trend I just sketched here is not followed consistently enough for that to work. Go by context instead.
By the way, your third sentence
We let N denote the set of natural numbers.
sounds slightly clunky to me; simply
Let N denote the set of natural numbers.
would be more straightforward.
(Note that actually neither of your sentences could usefully be used in a mathematical paper, since there is no real doubt that N and "the set of natural numbers" means the same, whereas differing traditions about whether zero counts as a natural number or not. Defining N to mean the set of natural numbers without revealing whether this set includes 0 for you is just a waste of ink and/or taunting the reader).