The associated Legendre functions for general l, m (i.e, l and m are not in general integers) can be written in terms of the hypergeometric function $_2F_1(a,b,c;x)$ thus: $$P^m_l(x) = (\frac{x+1}{x-1})^{\frac{m}{2}}\frac{1}{\Gamma(l+1) \Gamma(-l)}\sum^{\infty}_{n=0}\frac{\Gamma(l+1+n) \Gamma(n-l)}{\Gamma (1-m+n)\ n!}(\frac{1-x}{2})^n$$
I can see how this expression holds for non integer l, m as the gamma functions in the numerator and the denominator do not blow up to infinity and one simply obtains an infinite series. However, for the cases of integer l, m, the gamma functions will take negative integer arguments and thus tend to infinity. This issue happens to the gamma functions both in the numerator and denominator however (provided that $n\leq l$), and so these terms can be evaluated by taking the appropriate limit. For $n > l$, the gamma function in the denominator tends to infinity, however the one in the numerator doesn't; thus the series truncates to a polynomial of degree l as should be the case.
I'm having trouble explicitly finding what the above formula reduces to in the case of integer l, m. As I have written above, I can see that the correct behaviour arises in such cases (truncated polynomial instead of infinite series), however I am struggling to find the exact expression for such a case. As a start, I tried to obtain the standard Legendre polynomial expression ($m=0$) from the above representation; setting $m=0$ we obtain: $$P^0_l(x) = \frac{1}{\Gamma(l+1) \Gamma(-l)}\sum^{\infty}_{n=0}\frac{\Gamma(l+1+n) \Gamma(n-l)}{(n!)^2}(\frac{1-x}{2})^n$$
The awkward term is: $$\frac{\Gamma(n-l)}{\Gamma(-l)}$$
As I guess, I used (assuming this holds for negative arguments too): $$\Gamma(n+1)=(n+1)\Gamma(n)$$
Which implies, after a little rearrangement: $$\frac{\Gamma(n-l)}{\Gamma(-l)} = (-1)^n\frac{(l-1)!}{(l-n-1)!}$$
Which means that: $$P^0_l(x) = \frac{1}{l!}\sum^{\infty}_{n=0}\frac{(l+n)! (n-l)!}{(l-n-1)!\ (n!)^2}(-1)^n\ (\frac{1-x}{2})^n$$
This is clearly not correct, since it terminates at $n=l-1$, as opposed to $n=l$. I'd like to know what the original hypergeometric representation reduces to in the case of integer l, m (or at least integer $l$ with $m=0$ as a start).
Gradshteyn and Ryzhik, 'Table of Integrals, Series, & Products,' eq. 8.751.1 will work for your situation.