General Relativity: is Tangent Space Always Flat?
Short answer: yes each tangent space is flat.
In principle the tangent space is a vector space, not a Riemannian manifold, and so the concept of curvature technically doesn't apply if that's all you have. To define curvature you need to define parallel transport; for that, you need to think of the tangent space as a manifold, and that implies looking at the tangent spaces of the tangent space! And if you do that, the vector space structure gives you a canonical way to define parallel transport, and this parallel transport ends up being flat.
Finally, the solution to your paradox is simple: the curvature depends on derivatives of the metric, that is, on how it changes from tangent space to tangent space. The metric at a point is irrelevant because all vector spaces with an inner product are isometric; what matters is how it varies in space.
Edit in response to your edit: You're playing too fast and loose with the words. Differential geometry is complicated, and we need to be precise in how we speak.
You can always make any tangent space into Minkowski space by choosing an appropriate basis, not because it is flat, but because it is a vector space. The difference is subtle but important. A vector space has a single metric tensor: it takes pairs of vectors and returns a number. A manifold has a metric tensor field: a metric tensor at each point, which takes pairs of tangent vectors. The fact that the tangent space is flat is a red herring.
One definition of flatness (of a manifold) is that you can use a single coordinate system in which the metric tensor is everywhere Minkowski. This statement is different from the statement about the tangent space; here you're choosing a different basis at each point, which are related by coming from a single coordinate system. In a single tangent space, you only have one basis. And you can always have $g_{\mu\nu} = \eta_{\mu\nu}$ at a single point (and hence at a single tangent space), but making it so at every point with the same coordinate system may or may not be possible, and that's what flatness means.
TL;DR: your problem is not keeping track of the points where you evaluate things.
A metric tensor $g$ on a manifold $M$ is a smooth choice of scalar products $g_x$ on each vector space $T_xM$.
But every vector space $V$ is a manifold on its own right, and for $x \in V$, we have that $T_xV \cong V$. If $V$ equipped with a scalar product, which I'll call $h$, then $h$ may be regarded as a metric tensor on the manifold $V$, by assigning to each tangent space $T_xV$ the scalar product $h$ itself. Since this is a "constant" metric tensor, in the sense that in each tangent space you put the same scalar product (namely, $h$), the manifold $(V,h)$ is flat. The reason is very simple: the curvature depends on derivatives of the metric, and all of them are zero in this case. When one says that the vector space $(V,h)$ is flat, one actually means that the manifold $(V,h)$ is flat, in the sense explained above.
That being said, there are three manifolds with metric tensors into play here. Your spacetime $(M,g)$, Minkowski space $(\Bbb M^4, \eta)$, and for a given $x \in M$, the tangent space $(T_xM,g_x)$. The spacetime $(M,g)$ is not necessarily flat, but $(T_xM, g_x)$ and $(\Bbb M^4,\eta)$ are because of the previous paragraph.
The issue is that given coordinates for $(x^\mu)$ for $M$, sure, we may compute $g_{\mu\nu} = g(\partial_\nu, \partial_\nu)$ on the coordinate system domain. These functions are not in general constant. But when you fix a tangent space $T_xM$, every tangent vector $v \in T_xM$ is a combination $v = v^\mu\partial_\mu|_x$ of the coordinate vectors evaluated at the point $x$. And this gives rise to coordinates on $T_xM$, whose coordinate vectors are $\partial_\mu|_x$. In other words, I am saying that while $x \mapsto \partial_\mu|_x$ is a vector field on the coordinate neighborhood in $M$, the coordinate fields $$ T_xM \ni v \mapsto (\partial_\mu|_x)|_v \doteq \partial_\mu|_x \in T_xM \cong T_vT_xM $$are defined globally on $T_xM$, and they're constant. And the metric coefficients of the metric tensor $g_x$ (evaluated at $x$) on $T_xM$ are constant, and equal to $g_{\mu\nu}(x)$ (evaluated at $x$!!!).
And $(T_xM,g_x)$ is isometric to Minkowski space $(\Bbb M^4,\eta)$ because one can always choose normal coordinates for $M$ centered at $x$ for which $g_{\mu\nu}(x) = \eta_{\mu\nu}$. And this happens only at the point $x$. One can do this even if $(M,g)$ is not flat. On the other hand, $(M,g)$ being flat is equivalent to having $g_{\mu\nu} = \eta_{\mu\nu}$ along entire open neighborhoods, as opposed to only at a single point. Then one defines $T_xM \to \Bbb M^4$ by taking $\partial_\mu|_x$ to the canonical vectors $e_\mu$ in $\Bbb M^4$.
A tangent space is flat by definition. Often in general relativity a tangent space is described as simply a vector space defined at a point, so flatness does not apply. More strictly, according to the historical meaning of the word tangent, a tangent space is the affine space defined by the tangent vector space. Affine space is flat by definition.
It is also possible to define osculating spaces, which are not flat, but which share the same tangent space as the original manifold (I don't think these are interesting in general relativity, but the idea of an osculating space does have applications).
I am hoping that you will see that any conflict lies in an abuse of terminology. For example the tangent space of a sphere is a plane, it is not just the vector space which defines the directions in that plane.