I looked around a bit and found this paper (featuring no less than Shing-Tung Yau!) about the problem of generating meshes for the unit tangent bundle $UT(S^2)$ on the 2-sphere $S^2$. As you point out, $UT(M)$ probably isn't diffeomorphic to $M \times S^n$. For example in Yin's paper they point out that $UT(S^2)$ is non-trivial and can't be embedded in $\mathbb{R}^3$. However, locally the bundle is trivializable, and Yin's paper suggests that one approach could be to divide the manifold into trivializable patches, then explicitly compute the transition maps between patches.
You might be able to implement their idea to generate turn a mesh for $M$ into a mesh for $UT(M)$, which would have to be embedded into a much higher-dimensional Euclidean space. While many finite element libraries (deal.II among them) can solve PDEs on surfaces, I think they usually assume that it's a 1D or 2D surface embedded in 2D or 3D respectively. If you were working with something as simple as $UT(S^2)$, you'd have to embed it in $\mathbb{R}^4$, which probably falls outside the purview of many libraries.
You could also try to work only with a mesh for $M$ or, more in the spirit of the paper, meshes for a set of overlapping patches $M_\alpha$ such that $UT(M)$ is trivializable on each $M_\alpha$. Provided you have a way to calculate the transition maps, you can represent $f$ within each patch as a tensor product of a Galerkin basis function $\phi$ defined on $M_\alpha$ with the spherical harmonics of the appropriate dimension. You could then try and solve your PDE using, say, the Schwarz alternating method or some other domain decomposition method. Of course you'll also have to partition the mesh first. METIS is a great tool for this, but you could very well get a partition with a patch that isn't trivializable. It might be possible to then recursively partition non-trivial patches. Or it might be easiest to implement this yourself.