First, NCE and Negative Sampling (NS) serve different purposes:
 - NCE is for learning parameters $\theta$ of a modelled data distribution $p_m(x|\theta)$. 
 - NS is a trick to train a classifier when you only have `positive' training samples (one class).

So their purposes are different: NCE learns $p(x)$, NS learns $p(y|x)$, but mechanics are v.similar. 

**Simple explanation of NCE:**

NCE is used to estimate the parameters $\theta$ of a modelled data distribution $p_m(x;\theta)$ by learning a classifier (optimised w.r.t $\theta$) that distinguishes true data samples from artificially generated noise samples $x\!\sim\! p_n(x)$. When the classifier is optimised, the optimal $\theta^*$ gives the desired distribution $p_m(x;\theta^*)$.

**A naturally intuitive description of how this is different from Negative Sampling.**

NS works similarly, using a distribution of negative samples (labelled $0$ if the positive samples are labelled $1$) to train a classifier to distinguish the two sets. The difference is that the distribution $p_1(x)$ of the positive class is not typically wanted (as in NCE). For example, in Knowledge Graph link prediction, the classifier itself is wanted (which would not be useful if trained on only one class), in Word2vec, parameters of the classifier are used as word embeddings.

**I do have an intuitive understanding of negative sampling in the context of word2vec - we randomly choose some samples from the vocabulary V and update only those because |V| is large and this offers a speedup. Please correct if wrong.**

In my view this isn't quite right. Yes, negative sampling seems to have been implemented as a trick to reduce computation time, but it fundamentally changes the maths and means the model parameters - which become word embeddings - learn different values, subject to the noise distribution (e.g. see Levy & Goldberg (2014)). That seems to be an important aspect of why word2vec embeddings work so well.

**When to use which one and how is that decided? Is NCE better than Negative Sampling? Better in what manner?** 

Hopefully it's clear that you do pretty much the same thing for both (generate negative samples, train a classifier), but then it depends on what you are after. The key choice is the negative sampling distribution, which is pretty much an open research question.