Why can't General Relativity be written in terms of physical variables? I am aware that the field in General Relativity (the metric, $g_{\mu\nu}$) is not completely physical, as two metrics which are related by a diffeomorphism (~ a change in coordinates) are physically equivalent. This is similar to the fact that the vector potential in electromagnetism ($A_\mu$) is not physical. In electromagnetism, the equations can be written in terms of physical (i.e. gauge invariant) quantities -- the electric and magnetic fields. Why can't Einstein's equations similarly be written in terms of physical variables? Is it just that nobody has been able to do so, or is there some theorem/argument saying that it can't be done?
EDIT: Let me rephrase: Prove/argue that there is no explicit prescription that can be given which would uniquely fix coordinates for arbitrary physical spacetimes. I.e., show that there is no way to fix gauge in the full theory of general relativity (unlike in E&M or linearized GR where gauge can be fixed).
 A: Let us reformulate OP's question(v1) as follows.

Can General Relativity in $d$ bulk spacetime dimensions be written in terms of physical/propagating variables only?

The best one can do seems to be the following. For weak gravitational fields, one can write the curved metric 
$$ g_{\mu\nu}~=~\eta_{\mu\nu}+h_{\mu\nu}$$
as a sum of a flat Minkowski background $\eta_{\mu\nu}$ and a fluctuation part $h_{\mu\nu}$, which is symmetric and therefore contains $\frac{d(d+1)}{2}$ independent components.
Now use light-cone coordinates for the flat metric $\eta_{\mu\nu}$. The fluctuation part $h_{\mu\nu}$ then splits into $2d$ unphysical auxiliary variables (which can be eliminated), and $\frac{d(d-3)}{2}$ physical variables (=the traceless transversal part).
Reference: 
Barton Zwiebach, A first course in String Theory, Section 10.6.
A: If the notion of being physical is gauge-invariance, then the Ricci scalar in the Einstein-Hilbert action is a "physical" variable, in the same sense that $F_{\mu \nu} F^{\mu \nu}$~$(|E|^2-|B|^2)$ and $F_{\mu \nu} \tilde{F}^{\mu \nu}$~$(E \cdot B)$ are the fundamental gauge invariant quantities in pure Yang-Mills theories. But Einstein field equations are not built from an invariant in the same way that Yang-Mills field equations are not built from its invariants. Nevertheless, these field equations remain unchanged under gauge transformations of the fields, because the extra contribution is a total derivative term in the Lagrangian (unless the manifold has a boundary, in which case a Gibbons-Hawking term has to be added to the Lagrangian to absorb the extra contribution)
Note that $E$ and $B$ fields themselves are not gauge invariant as your question seems to suggest. 
I am not sure if Ricci curvature is the only fundamental invariant of Riemannian manifolds. Is Yamabe invariant fundamental? Would be nice if someone could post a list of (fundamental and derived) invariants.
A: Wigner always complained about people who used the word « invariant » (this was, of course, in the context of Special Relativity): he said one should say that the principle of relativity requires « covariance,» not invariance.  Einstein's own papers on GR tend to carry out Wigner's request: the theory of GR (which is more general than Einstein's theory of gravity or his field equations) is always expressed as the demand for covariance with respect to arbitray coordinate changes.  Now another myth, according to me, is that relativity requires that the laws be transformed by the group into other laws « of the same form.»  This is just verbiage until you define what you mean by « form,» and even worse, it would then be just linguistics instead of physics.  Examining Einstein's practice in this matter, and his occasional explicit pronouncements, GR really says: the laws of physics must take the form of equating a tensor to zero.  This works because the tensor has the same covariance properties under change of coordinates as zero does.
Therfore the requirement of covariance has nothing to do with $f^* g$ for $f$ a diffeomorphism and $g$ a tensor field.  This can be seen another way: for Einstein, $M$ is not physical, it is $g$ that is physical.  Hence $f$ has to be regarded as a change of coordinates which does not actually move the mathematical points of $M$.  The formula which mathematicians use for $f^*g$ has to be reinterpreted as coming from $f$ as the transition function between two charts of $M$ around a given point $x$, i.e., qua diffeomeorphism, it is the identity.  Let me put this another way: a change of coordinates does not move the points, it just changes the charts.  Therefore, a change of coordinates is the trivial identity map when you look at it in the mathematicians' invariant, coordinate free definitions of $M$, $f$, $f^*$, and tensors.
And now let me put this a third way, tying it up with Wigner's point of view in Special Relativity: what GR requires is that $g_{\mu\nu}$ be covariant, and in your set-up, this is the requisit for $f^* g$ to even be well-defined.  This is what is needed to define a group action of diff($M$) on the set of metric tensors, and is the strict analogy to Wigner's requiring that one work with a representation of the Lorentz group.  Covariance means the group action is defined, not that it is trival.
That is one reason why diff($M$) is not a good analogy to the gauge transformations of EM or Weyl's theory.  But there is another: in EM, the relation between the potential and the field is one thing, but the relation between $g_{\mu\nu}$ and the Christoffel symbols (the affine connection) is quite another.  Yes, mathematically the two relations have something similar but from the stanpoint of the symmetries involved there is a crucial difference: the metric field is covariant (a tensor) but the Christoffel symbols are not, whereas in EM, the fields transform well under the Lorentz group too.  Hence, by the philosophy of GR, the metric tensor field has to be regarded as more physical than the Christoffel symbols even though everyone, and Einstein too, calls the metric the « gravitational potential » and the Christoffel symbols the « gravitational field.»  This suggested analogy just shouldn't be taken too seriously, and in fact, Einstein himself constantly oscillates between this terminology and the seemingly contradictory calling the metric tensor field « the gravitational field,» which, at least to me, suggests he didn't think the distinction was that important.
And there is another: in EM we can only measure differences in potentials, of course, so that is why we introduce a choice of gauge and gauge transformations.  But (pace extreme positivists), we can in principle measure the metric tensor using light rays and clocks and travelling rods, as explained by Weyl and Einstein.  (Of course only because this is an ideal classical world so we can make the masses negligible...).  Einstein's equations are irrelevant!  Just as, in discussion of what a choice of gauge is and what a gauge transformation is in EM, Maxwell's equations were irrelevant! That is, the definition or concept of gauge and gauge transformation make sense, and one can think about their physicality and desirability, even without considering Maxwell's equations.  And following that road, one could first decide, on physical grounds, what the gauge transformations were, and then search for the Law of Nature that was gauge invariant in that sense.
But the Christoffel symbols, although they can obviously be measured in a sense since they can be calculated from the metric, are not physical because they are not covariant.  Too much argument about what « physical » means would be philosophical, but all I want to really insist on is that for GR, if something isn't even covariant then it is not objective and « real », so this destroys the analogy with gauges in EM all by itself.
Having now disposed of diff($M$), I briefly state what everyone already knows: for any Riemannian or Lorentzian manifold, there exists a gauge which makes the metric field a tensor, this is explained by Weyl in his book, except he calls it a calibration.  So that answers your question for classical GR.  
EDIT for the comment by the OP.
The principle of general relativity is that there is no natural way to distinguish between one set of coordinates and another.  That is the whole point of GR, its philosophy, if you will.  There is no physical criterion to use to say one coordinate system is better than another.  
Perhaps you already knew that, so let us consider choices which have no physical motivation or significance but look pretty.  E.g., geodetic coordinates.  For any $M$ and any given point $p$ you can define local coordinates in a small neighbourhood of $x$ in $M$ which are geodetic in the sense that they nicely describe parallel transport along the coordinate axes.  But they have no global significance, they don't do anything for the whole potato, only for the one point $x$, because as soon as you parallel transport something a finite distance away from $x$, what you get depends on the path you took to get there.  They have « local » significance, not « global » significance, and the reason there is a difference between local and global is the geometric fact of non-integrability, which is inherent in the curved geometry of $M$.  Only if $M$ is flat is the situation « integrable.»  In fact, this is the definition of curvature.  Curvature is defined as the deviation from integrability of this parallel transport you do in a geodetic coordinate system.  
So the answer to your question is: there is no coordinate system in the large with nice properties, unless $M$ is flat.  
You see, the question was confused between choosing a gauge and choosing a coordinate system, these are not the same things.  If this confusion is straightened out, it gets two different answers: If $M$ is pseudo-Riemannian, yes there exists a choice of gauge which means the metric can be represented by a tensor, not a twisted tensor.  But no, there does not exist any prescription for coordinates which have nice properties in the large unless $M$ is flat.
