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

Firstly, NCE and Negative Sampling (NS) serve different purposes:
 - NS is a generic trick used to train a classifier if you only have training samples from one `positive' class (e.g. labelled $y\!=\!1$);
 - NCE is a method to learn parameters $\theta$ of a model $p_m(x;\theta)$ of a true data distribution $p_d(x)$. 

So their purposes are different: NS learns to approximate a conditional label distribution $p(y|x)$, NCE approximates $p_d(x)$. Since NCE uses negative samples (or a *noise distribution*) to learn $p_m(x|\theta)$ it can be seen as a case of NS. 

NS is generic as it can be used just to train the classifier (e.g. in Knowledge Graph link prediction), to learn embeddings/representations (e.g. *word2vec*), or as a step in NCE. NCE is a special case of NS where $p_n(x)$ is not just sampled from, but the actual density $p_n(x)$ must be computed.

**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 corresponding $\theta^*$ gives the desired distribution $p_m(x;\theta^*)$.

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

NS is not as clearly defined as NCE, but typically refers to when artificially generated samples, $x\!\sim\!p_n(x)$, labelled $y\!=\!0$ (i.e. $p_n(x)\!\equiv\!p(x|y\!=\!0)$) are used to train a classifier $f(x;\theta)$ that distinguishes them from positive samples, $x\sim p_d(x)\!\equiv\!p(x|y\!=\!1)$, i.e. once trained $f(x;\theta)\!\approx\!p(y\!=\!1|x)$. 

If the classifier uses the sigmoid function $\sigma(t) \!=\! (1\!+\!e^{-t})^{-1}$, i.e. $f(x;\theta) \!=\! \sigma(g(x;\theta)$), then implicitly $g(x;\theta) \!\approx\! \log\tfrac{p(y=1|x)}{p(y=0|x)} 
\!=\! \log\tfrac{p(x|y=1)p(y=1)}{p(x|y=0)p(y=0)} 
\!=\! \log\tfrac{p_d(x)}{p_n(x)k}
$, where $k\!=\!\tfrac{p(y=0)}{p(y=1)}$. Whilst this reformulation may not be of interest generally, it explains e.g. why *word2vec* embeddings learn pointwise mutual information (PMI). 

In NCE, $\theta$ is used to specifically parameterise $p_d(x)$ (not the whole log ratio), i.e. $p_m(x;\theta)\!\approx\!p_d(x)$. Making that substitution and reversing the above equation gives a formula that approximates $p(y\!=\!1|x)$ in terms of $p_m(x;\theta), p_n(x)$ and $k$ that fits into a binary cross entropy loss function. When that loss is minimised $p_m(x;\theta)$ is the best approximation of $p_d(x)$.

**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 (PMI) due to the choice of noise distribution (see Levy & Goldberg (2014)). That seems to have been an important aspect of why word2vec embeddings work as they do.

**When to use which one and how to decide? Is NCE better than NS? Better in what manner?** 

Hopefully it's clear that you do the same thing in either case (generate negative samples, train a classifier). Whether you call it NCE or NS depends on what you want from it. A key choice affecting performance in all cases is the negative sampling distribution. The NCE paper looks into this but (I believe) the optimal choice is an open research question.