An algorithm specifies a method to get from a given input to a desired output that has a certain relation with the input. We say that this algorithm is deterministic if at any point, it is specified exactly and unambiguously what the next step in the algorithm is that must be performed as part of that method, potentially dependent on the input or the partial data computed so far, but always uniquely identified.
Nondeterminism means that some part of the algorithm is left under or even unspecified. For example, "int i = an even number between 0 and n" is underspecified. This means there is no unique behavior that is specified at this point.
For this distinction to be useful, you need the (usual) concept of 'correctness' for (deterministic) algorithms, which informally is that "the algorithm always computes what I want it to compute". It then becomes interesting to think about what correctness would mean for nondeterministic algorithms, which must take into account the choices possible in underspecified instructions.
There are two ways of defining correctness for nondeterminism. The first one is rather simple and less interesting, for which correctness means "the algorithm always computes what I want it to compute, for all sequences of choices I am allowed to make". This sometimes occurs if an author of a bit of pseudocode is too lazy to pick a number and says "pick any even number between 0 and n", when "pick 0" would have made the algorithm deterministic. Essentially, by replacing all nondeterminism by the result of some choice you can make the algorithm deterministic.
This is also the 'nondeterminism' referred to in your second paragraph. This is also the nondeterminism in parallel algorithms: in these algorithms you are not quite sure what execution precisely looks like, but you know that it will always work out, no matter what happens exactly (otherwise your parallel algorithm would be incorrect).
The interesting definition of correctness for nondeterministic algorithm is "the algorithm always computes what I want it to compute, for some sequence of choices I am allowed to make". This means that there may be choices that are wrong, in the sense that they make the algorithm produce the wrong answer or even go in an infinite loop. In the example "pick any even number between 0 and n", perhaps 4 and 16 are right choices, but all other numbers are wrong, and these numbers may vary depending on the input, the partial results and the choices made so far.
When used in computer science, nondeterminism is usually limited to nondeterministically choosing either a 0 or a 1. However, if you pick many such bits nondeterministically, you can generate long nondeterministic numbers or other objects, as well as make nondeterministic choices, so this hardly (if ever) limits its applicability - if applicability is limited, nondeterminism was too powerful in the first place.
Nondeterminism is a tool that is exactly as powerful as a certificate-based deterministic algorithm, that is, an algorithm that checks a property given an instance and a certificate for that property. You can simply nondeterministically guess the certificate for one direction, and you can give a certificate that contains all the 'right' answers for the nondeterministic guesses of 0 and 1 of your program for the other direction.
If we throw running time into the mix, then things become even more interesting. The running time of a nondeterministic algorithm is usually taken to be the minimum over all (right) choices. However, other choices may lead to a dramatically worse running time (which can be asymptotically worse or even arbitrarily worse than the minimum), or even an infinite loop. This is why we take the minimum: we do not care about these weird cases.
Now we get to randomized algorithms. Randomized algorithms are like nondeterministic algorithms, but instead of 'allowing' the choice between 0 and 1 at certain points, this choice is determined by a random coin toss at the time that the choice has to be made (which may differ from run to run, or when the same choice has to be made again later on during the execution of the algorithm). This means that the result is 0 or 1 with equal probability. Correctness now becomes either "the algorithm nearly always computes what I want it to compute" or "the algorithm always computes what I want it to compute" (just the deterministic version). In the second case the time the algorithm needs to compute its answer is usually 'nearly always fast', contrasting with a deterministic 'always fast'.
Contrasting the three: deterministic algorithms exactly specify the answer to the choice, nondeterminism leaves it completely open, but tells you a 'right' answer exists, and randomization leaves the answer up to chance. Note that you can just guess the right coin tosses, which gives rise to a hierarchy between these three: nondeterminism is as powerful as randomization, which in turn is as powerful as determinism, or, with respect to polynomial time, $P \subseteq ZPP \subseteq NP$. In this setting, no proofs are known whether any is strictly more powerful than another.