[I've added this answer as I think previous ones miss the main theoretical gist.]

Firstly, 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.

**Intuition for negative sampling in word2vec: we randomly sample from the vocabulary V and update only those as |V| is large and this offers a speedup. 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 to decide? Is NCE better than NS? Better in what manner?** 

So, hopefully it's clear that you do pretty much the same thing to start with in either case (generate negative samples, train a classifier). Whether you call it NCE or NS depends on what you do next. A key choice affecting performance in both cases is the negative sampling distribution (note: you must be able to evaluate $p_n(x)$ for NCE), the best choice is pretty much an open research question.