OP wrote(v3):
[...]This is a contradiction as in this case the dimension of the state space does not have a well-defined cardinality.
User twistor59 has already in his answer explained that spherical harmonics
$$Y_{\ell m}(\theta, \varphi)~=~\langle \theta, \varphi |\ell, m \rangle $$
live on the two-sphere $S^2$ parametrized by the coordinates $(\theta, \varphi)$; and how we may view $\mathbb{R}^3\backslash\{\vec{0}\}\cong ]0,\infty[\times S^2$ as a half-line times a two-sphere using spherical coordinates $(r,\theta, \varphi)$.
So in this answer we will just mention that the alleged contradiction (in counting the dimension of the state space) has a simpler analogue for the one-sphere $S^1\cong\mathbb{R}/2\pi\mathbb{Z}$, i.e. the circle. Recall that functions $\psi(\theta)=\psi(\theta+2\pi)$ on the circle $S^1$ are periodic functions of some angular position variable $\theta\in[0,2\pi[$. A countable basis $(|m\rangle )_{m\in\mathbb{Z}}$ is via Fourier series
$$\psi(\theta)~=~\sum_{m\in\mathbb{Z}} c_m e^{im\theta},
\quad e^{im\theta} ~=~\langle \theta| m \rangle,\quad c_m~=~\langle m |\psi\rangle,\quad \psi(\theta)~=~\langle \theta |\psi\rangle.$$
The Hilbert space is a $L^2$-space
$$H~:=~L^2(S^1)~\cong~\ell^2(\mathbb{Z})~:=~\left\{(c_n)_{n\in\mathbb{Z} } ~\mid~ \sum_{m\in\mathbb{Z}} |c_n|^2 < \infty\right\}, $$
which is isomorphic to the set of square integrable series. See also e.g. this Phys.SE post.
A continuous basis is $(|\theta\rangle )_{\theta\in[0,2\pi[}$ does not belong to the Hilbert space $H$ but rather to the so-called rigged Hilbert space. See also e.g. this Phys.SE post. So there is no contradiction. We are just talking about two different state spaces. Essentially the same explanation (for the alleged contradiction in counting the dimension of the state space) also applies to e.g. the two-sphere $S^2$ and the three-space $\mathbb{R}^3$.