Reason for vanishing of the covariant derivative of energy-momentum tensor of matter in general relativity Einstein assumed in the derivation of his field equations that the covariant derivative (defined through the metric) of the energy momentum tensor of matter is zero, i.e.
$$\nabla_{\mu}T^{\mu\nu}=0,$$
no matter how distorted the spacetime is.
It seems such a conclusion cannot be reached at via Nöther's theorem (since the metric is itself changing over spacetime). So my question is how did he have this insight then, and how would one justify the correctness of this assumption in retrospect from a Lagrangian point of view now? 
If it's based on the existence of infinitesimal coordinate transformations that fix the boundary of some volume in spacetime, then would this also imply that the energy momentum tensor of any field will always have zero covariant derivative with or without gravity?

Edit: Previous form of the question had an abuse of language, viz., that I referred to the "vanishing of the covariant derivative of the energy-momentum tensor" as "energy momentum tensor is covariantly conserved". This was rightly pointed out by Ben Crowell in his answer and, I've edited the question and made it mathematically precise for the sake of clarity.
 A: This isn't a fact about general relativity, it's a fact about special relativity. Based on hundreds of years worth of experiments, we know that the energy-momentum four-vector is conserved locally. This means that the stress-energy tensor has zero divergence. (The stress-energy tensor isn't conserved. What's conserved is the energy-momentum four-vector.)
If you want a deeper theoretical justification for conservation of the energy-momentum in special relativity, then you can appeal to Noether's theorem for translations. It doesn't have anything to do with more general coordinate transformations.
Once an equation like $\partial_\mu T^{\mu\nu}=0$ is established in special relativity, then carrying it over into general relativity is normally a trivial process. We just replace partial derivatives with covariant derivatives. Basically this is just the fact that GR is the same as SR, locally.
What is nontrivial is carrying over global things, like an equation stating the conservation of energy-momentum in an asymptotically flat spacetime. This kind of thing generally just doesn't work, the problem being that parallel transport is path-dependent, so we can't do things like summing momenta over a region of space.
A: *

*Diffeomorphism invariance implies (via Noether's 2nd theorem) that 
$$\nabla_{\mu} T^{\mu\nu}~\approx~0.\tag{1}$$
Perhaps surprisingly, there are no conserved quantities associated with the identity (1) per se for generic spacetime metric $g_{\mu\nu}$. 

*However, if the metric $g_{\mu\nu}$ has a Killing vector field $K^{\mu}$, then the $4$-current
$$J^{\mu}~:=~T^{\mu\nu} K_{\nu} \tag{2}$$
satisfies a continuity equation
$$  \nabla_{\mu} J^{\mu}~\approx~0,\tag{3}$$
which leads to a conserved quantity in the standard fashion.

*See e.g. my related Phys.SE answer here for more details.
