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} $$$$ \sum_{j=0}^{k}\binom{k}{j}^{3}=\sum_{\ell=k/2}^{k}\binom{k}{\ell}^{2}\binom{2\ell}{k} $$ 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} $$