Let me try to break down the question into several parts, in the context of seeking a gravity theory that satisfies an action principle. That is, we are looking for a Lagrangian density that describes the theory.
First, the equivalence principle tells us that the gravitational field must couple universally to matter.
Second, the theory has to be (at least) a tensor theory. A vector theory would yield a repulsive force between like charges. A scalar theory would produce the wrong sign for potential energy, and this would violate observations concerning the equivalence principle. A theory with half-integral spin is even worse, as the exchange of such a particle cannot result in a static inverse-$r$ force. (This is explained very nicely in Feynman's Lectures on Gravitation -- Addison-Wesley, 1995.)
So we are looking for a tensor theory that couples universally to matter.
The simplest field that couples universally to matter would be the metric: it couples universally and minimally, meaning that the metric is used to form inner products and provides the volume element for the action integral, and nothing else.
So then, this suggests that we are looking for a metric theory. Variations of the Lagrangians of matter fields will yield their corresponding stress-energy tensors... so far so good. On the other side is the gravitational field. We wish to make sure that whatever field equations we obtain, in the weak field limit we get back Poisson's equation for gravity. So... what kind of an invariant scalar quantity, formed from the metric tensor and its derivatives, can represent the gravitational field?
For starters, it has to contain at least first derivatives of the metric tensor, otherwise we will not get the second derivative in the field equations that is required to reproduce Poisson's equation. It may contain second derivatives of the metric, but we have to be careful: if the resulting field equations contain higher derivatives, we may run afoul of the Ostrogradsky instability.
One of the simplest scalar quantities that we can form from the metric and its derivatives is the curvature scalar. If we make the curvature scalar the gravitational Lagrangian, the resulting field equations are Einstein's: this is general relativity.
A trivial and permissible modification is to add a constant to the curvature scalar. (This changes the field equations because even a constant is multipled by the volume element, formed from the metric, in the action integral.) The resulting field equations are again Einstein's, but with a cosmological constant.
Other scalar quantities formed from the metric do not reproduce Poisson's equation. For instance, there is conformal gravity, in which the gravitational Lagrangian is formed from the conformal (Weyl) tensor. In the weak field approximation, this results in a quartic equation of motion, and it is incompatible with the notion of a perfect fluid approximation of nonrelativistic matter. Its proponents address this criticism by arguing that the underlying fermion fields are not perfect fluids, but I find that argument unpersuasive.
What if we replace the curvature scalar with a scalar function of it in the Lagrangian? These would be the so-called $f(R)$ theories. They turn out to be more-or-less equivalent to another family, the family of scalar-tensor theories: in this case, an additional scalar field is introduced that also couples minimally, in essence replacing the gravitational constant with a field.
These and many other metric theories of gravity (metric meaning no direct coupling between additional fields and matter, so matter particles move along geodesics) can be studied using the so-called parameterized post-Newtonian (PPN) formalism. Described in detail in Clifford Will's book (Theory and experiment in gravitational physics, Cambridge, 2000) this formalism has as many as 11 parameters that can be subjected to constraints derived from observation. To date, general relativity wins: in all precision gravitational experiments, constraints are zeroing in on GR, and other theories are either excluded or require ridiculously fine-tuned parameters.
These considerations, of course, were not available to Einstein back in 1915. What he was seeking was a theory in the form of $G_{\mu\nu}=8\pi GT_{\mu\nu}$ where $G_{\mu\nu}$ is some tensor that is a) formed from the metric, and b) satisfies a conservation law (i.e., it is divergence-free). The first condition was a reflection on the fact that the equivalence principle implies that the theory has to be geometrical: i.e., given that material particles respond to gravity the same way, independent of their composition, the effects of gravity can be transformed away, at least locally, by a geometric transformation. As for the second condition, it was a reflection of the fact that the matter stress-energy tensor, $T_{\mu\nu}$, is itself divergence-free.
He had many false starts: he tried $G_{\mu\nu}=R_{\mu\nu}$ (works fine in the vacuum but $R_{\mu\nu}$ is otherwise not divergence-free) and he was not aware of the Bianchi identities that, when contracted, yield $(R^{\mu\nu}-\frac{1}{2}g^{\mu\nu}R)_{;\mu}=0$. Nonetheless, in late 1915, he stumbled upon $G_{\mu\nu}=R_{\mu\nu}-\frac{1}{2}g_{\mu\nu}R$ and the theory was born. However, it was not Einstein but Hilbert who derived this form of the left-hand side of the Einstein equations from what is today called the Einstein-Hilbert Lagrangian, ${\cal L}_G=R$.
And lest we forget, Einstein's original goal was not to seek a new theory of gravity. What he was seeking was a generalization of the theory of relativity (later to be known as the special theory) to accelerating frames. It was the realization that the equivalence principle means that acceleration and gravity cannot be distinguished that led him to the conclusion that the theory necessarily must account for gravity. Even the name reflects this: Einstein's theory is the general theory of relativity.
