The answer to your question is affirmative in the following sense:
In the Riemann normal coordinates at $p$ the coefficients of the Taylor expansion of the metric $g_{ij}(x)$ are polynomials in the Riemann tensor at $p$ and its covariant derivatives at $p$. [Assuming the proof in this random thing I googled[a] is correct, starting at (5.1)].
I think this is the correct formalization of your conjecture in the sense that if we are making a tensor out of $g$ the only thing we can use are $g$ and its expansion in normal coordinates. I'll maybe try to write out why I think this is case.
BTW, the local condition is very necessary, since otherwise we could define things like the length of the shortest loop containing $p$ that is in a certain homotopy class, which clearly "depends only on the metric" but is not made out of polynomials the curvature.
Added after this answer was accepted
For those interested, I asked a question on Math SE that contains what I believe to be the correct formalization of the question: "What tensors can I produce from the metric tensor?" “Natural” constructions of tensor fields from tensor fields on a manifold
[a]: Guarrera, D.T., Johnson, N.G., Wolfe, H.F. (2002) The Taylor Expansion of a Riemannian Metric
$\mbox{ } $ $\mbox{ } $ $\mbox{ } $ $\mbox{ } $ $\mbox{ } $ $\mbox{ } $ $\mbox{ } $ http://www.rose-hulman.edu/mathjournal/archives/2002/vol3-n2/Wolfe/Rmn_Metric.pdf
@Prahar is right, the variation of the Christoffel symbol is a tensor, even if the Christoffel itself is not. We have
$\delta \Gamma^\rho_{\mu\nu}=\frac{1}{2}\delta\bigg(g^{\rho\alpha}(2\partial_{(\mu}g_{\nu)\alpha}-\partial_\alpha g_{\mu\nu})\bigg)=\frac{1}{2}\delta g^{\rho\alpha}(2\partial_{(\mu}g_{\nu)\alpha}-\partial_\alpha g_{\mu\nu})+ \frac{1}{2}g^{\rho\alpha}(2\partial_{(\mu}\delta g_{\nu)\alpha}-\partial_\alpha \delta g_{\mu\nu})$
where $A_{(\mu\nu)}=\frac{1}{2}(A_{\mu\nu}+A_{\nu\mu})$. Using $\delta g^{\rho\alpha}=-g^{\rho\gamma}g^{\alpha\delta}\delta g_{\gamma\delta}$ we have:
$\delta \Gamma^\rho_{\mu\nu}=\frac{1}{2}g^{\rho\alpha}(2\partial_{(\mu}\delta g_{\nu)\alpha}-\partial_\alpha \delta g_{\mu\nu}-2\Gamma_{\mu\nu}^\beta\delta g_{\alpha\beta})$
The Christoffel then combines nicely with the standard derivative to give a covariant tensor (the other Christoffel symbols cancel each other)
$\delta \Gamma^\rho_{\mu\nu}=\frac{1}{2}g^{\rho\alpha}(2\nabla_{(\mu}\delta g_{\nu)\alpha}-\nabla_\alpha \delta g_{\mu\nu})$.
So to answer the original question, we finally have:
$\nabla_\mu V_\nu=\nabla_\mu \delta V_\nu-\frac{1}{2}g^{\rho\alpha}(2\nabla_{(\mu}\delta g_{\nu)\alpha}-\nabla_\alpha \delta g_{\mu\nu})A_\rho$
Remember that we did not assume anything on $V_\mu$. Depending on the problem, it is then possible to integrate by parts to isolate $\delta g_{\mu\nu}$ and obtain the energy momentum tensor.
Best Answer
No. Covariant derivatives act on tensor fields of arbitrary rank, but the object $\partial g$ whose components in an arbitrary coordinate chart are given by $$\big(\partial g\big)_b^{\ \ \mu \nu}:= \partial_b g^{\mu\nu}$$ is not a tensor field (nor do the Christoffel symbols $\Gamma^i_{jk}$ constitute the components of a tensor, as you say).