My text tells me that Legendre's polynomial is the exact solution to this ODE above. However, I know that Legendre's polynomial should be the solution to Legendre's differential equation 
I know that we can solve the above equation by power series and the resulting series for the solution terminates for specific value of n. For these value of n, we have solution in closed form.
I I know that I can do local analysis on the firs ODE and solve it approximately near the point 0 by expanding out the sine and cosine in terms of Taylor series about 0 and neglecting power higher than $x^2$. If I do that, I end up with a solution similar to Legendre's polynomial. But asymptotic solution is not exact solution. Why do people say the solution to Schrödinger's equation of hydrogen atom is an exact solution?

The solutions to the first equation are Legendre polynomials of $\cos\theta$. In other words, the solutions are $P_{l}^{m}(\cos\theta)$ (up to normalization factors) rather than $P_{l}^{m}(x)$.
Also, we are dealing with a more general class of Legendre polynomials called associated Legendre polynomials which are solutions to the PDE
$$ \frac{d}{dx}\left((1-x^{2}) \frac{dP_{l}^{m}}{dx}\right) + l(l+1)P_{l}^{m}(x) - \frac{m^{2}}{1-x^{2}}P_{l}^{m}(x) = 0. $$
See https://en.wikipedia.org/wiki/Associated_Legendre_polynomials.
This means one should be able to derive the above equation from your first equation by substituting $x = \cos\theta$. I will do this here for completness.