Sorry I am currently somehow confused by the following:
The Legendre polynomials $(P_l)$ form an ONB of $L^2(0,\pi)$ and the complex exponentials $(\frac{1}{\sqrt{2\pi}}e^{in \theta})_n$ form an ONB of $L^2(0,2\pi)$.
So $(P_l) \otimes (\frac{1}{\sqrt{2\pi}}e^{in \theta})_n$ should form an ONB of $L^2(0,\pi) \otimes L^2(0,2\pi),$ On the other hand, we know that the spherical harmonics form an ONB of the tensor product space $L^2(0,\pi) \otimes L^2(0,2\pi),$
but they are not just combintions of the Legendre polynomials and the exponentials but rather combinations of the associated(!) Legendre polynomials $(P_l^m)$ and the exponentials. So do the associated Legendre polynomials also form an ONB of something or how do they come into play when talking about the tensor product space?
So something is strange about this.
The key thing to recognize here is that an orthonormal basis on a space is very much not unique. For example, by rescaling the $x$ axis by a factor of two, you could adjust the Legendre polynomials to form an orthonormal basis on $L^2(0,2\pi)$, while at the same time the complex exponentials $\frac1{\sqrt{2\pi}}e^{inx}$ also form an orthonormal basis on this same space. The consequence is that each of these orthonormal bases can be expressed in terms of the other. In this case, a complex exponential $e^{inx}$ can be written in terms of its Taylor series $e^{inx}=\sum_{k=0}^\infty \frac{i^kx^k}{k!}$, and each of the monomials $x^k$ can be expressed as a linear combination of Legendre polynomials of degree at most $k$. Conversely, each Legendre polynomial has a Fourier series representation which expresses it in terms of the functions $e^{inx}$.
The consequence is that the spherical harmonics may be expressed in it terms of whichever orthogonal bases you wish to use for the two factors in the tensor product $L^2(0,\pi) \otimes L^2(0,2\pi)$ (and there are infinitely many choices). However, if we are thinking of these as functions on the sphere, then such tensor-product bases may be less convenient than the spherical harmonics because they will not behave as nicely under the symmetries of the sphere (i.e., under the action of the orthogonal group $O(3)$).