Here as an approach. 
It is known that:
$P_{n}(x) = \sum_{k=0}^{n}\binom{n}{k}\binom{-n-1}{k}\left(\frac{1-x}{2}\right)^{k}$  (see for example  <http://en.wikipedia.org/wiki/Legendre_polynomials>)
Therefore these expressions are equal 
$$
\sum_{k=0}^{n}\binom{n}{k}\binom{n+k}{k}\sum_{j=0}^{k}\binom{k}{j}^{3}=\sum_{k=0}^{n}\binom{n}{k}\binom{-n-1}{k}\frac{1}{4 \pi^{2}}\int_{-\pi}^{\pi}\int_{-\pi}^{\pi}\left(\frac{1-g(x,y)}{2}\right)^{k}dydx
$$
if 
$$
\sum_{j=0}^{k}\binom{k}{j}^{3}=\frac{1}{4 \pi^{2}}\int_{-\pi}^{\pi}\int_{-\pi}^{\pi}\left(\frac{g(x,y)-1}{2}\right)^{k}dydx
$$
One can see that 
$$
\left(\frac{g(x,y)-1}{2}\right)^{k} = 4^{k} (\cos^{2}x + \cos x \sin y )^k
$$
Therefore we get 
$$
\frac{1}{4 \pi^{2}}\int_{-\pi}^{\pi}\int_{-\pi}^{\pi}\left(\frac{g(x,y)-1}{2}\right)^{k}dydx = \frac{4^k}{4\pi^{2}}\int_{0}^{2\pi}\int_{0}^{2\pi}\sum_{j=0}^{k}\binom{k}{j}\cos^{2k-j}x \sin^{j} y dxdy
$$

Since 
\begin{align*}
\int_{0}^{2\pi} \cos^{m} x dx=\int_{0}^{2\pi} \sin^{m} x dx = \frac{2\pi} {2^m}\binom{m}{m/2} \quad \text{for} \quad m \quad \text{even, otherwise =0}
\end{align*}
We get 
$$
\frac{1}{4 \pi^{2}}\int_{-\pi}^{\pi}\int_{-\pi}^{\pi}\left(\frac{g(x,y)-1}{2}\right)^{k}dydx  = \sum_{\ell=0}^{k/2}\binom{k}{2\ell}\binom{2\ell}{\ell}\binom{2(k-\ell)}{k-\ell}
$$

and now we want to show that 
$$
\sum_{j=0}^{k}\binom{k}{j}^{3}=\sum_{\ell=0}^{k/2}\binom{k}{2\ell}\binom{2\ell}{\ell}\binom{2(k-\ell)}{k-\ell}
$$
The last equality follows from the identity:
$$
\sum_{j=0}^{k}\binom{k}{j}^{3}=\sum_{\ell=k/2}^{n}\binom{k}{j}^{2}\binom{2j}{n}
$$ 
See for example http://arxiv.org/pdf/math/0311195v1.pdf formula (2).
because 
$$
\binom{k}{2\ell}\binom{2\ell}{\ell}\binom{2k-2\ell}{k-\ell}=\binom{k}{k-\ell}^{2}\binom{2k-2\ell}{k}
$$