Here is what Odifreddi says on the issue:
"Our model of a Turing machine is deterministic,
in the sense that the instructions are required to be consistent
(at most one of them is applicable in any given situation).
Randomizing elements in computing devices were introduced early on by
Shannon  and De Leeuw, Moore, Shannon and Shapiro .
There are basically two models.
Nondeterministic Turing machines behave,
in an ambiguous situation
where conflicting instructions might be applicable,
by randomly choosing one of them:
their computational power, at least for 0,1-valued functions (sets),
does not exceed the power of deterministic ones.
Probabilistic machines differ from nondeterministic ones in that
the next state has a probability, and thus conflicting instructions
do not have the same chance of being chosen by the machine."
[P. Odifreddi, Classical Recursion Theory, Vol. 1, page 50]
Note that the notion of nondeterminism in the sense of
"there exists + verifier" existed in computability theory long before complexity theory,
e.g. Kleene's normal form, arithmetical hierarchy.
Other models of computation like
Post canonical systems (known at least since 1943) and grammars are also nondeterministic.
I think one can even push the notion to the time of Hilbert's epsilon calculus and choice operators.
About NP, I asked Steve Cook.
The name NP for the class of nondeterministic polynomial-time computable problems
was introduced by Richard Karp in his famous 1972 paper.
Cook refers to the class of polynomial time nondeterministic Turing machine computable problems in his famous 1971 paper which defines polynomial time reductions and shows that there are complete problems, but without giving a name to the class.
Before his paper there was not much interest in problems computable in polynomial time by nondeterministic Turing machines,
only after Karp's paper it became clear that so many natural problems are in NP.
After Cook's paper some people got interested,
particularly two who got interested early on (before Karp's paper came out)
were Michael Rabin and Allan Borodin.
Karp's 1972 paper surprised people by showing how pervasive NP-completeness is
among natural problems.