There are several major ideas that went into general relativity: finite speed of gravity propagation, not necessarily Euclidean geometry of space, identification of inertia and gravity, mechanics as geometry, and uniformity of physical laws in all coordinate frames, even accelerated ones (general covariance). The last two ideas are specifically Einstein's, and only emerged after he formulated special relativity in 1905. The equivalence of inertia and gravity, "the happiest thought of my life", occured to him in 1907, but he did have a 19th century inspiration in Ernst Mach, who vaguely speculated that inertial mass arises from the body's interaction with the rest of the universe. But the first two ideas have the deepest 19th century roots.
Dissatisfaction with action at a distance goes back to Newton, but the first physicist to systematically consider a gravity theory with finite propagation speed was Laplace in his Celestial Mechanics (1799). He introduced velocity dependence, so called non-zero latency, when forces are directed to retarded positions of bodies rather than the current ones... and discovered that planets will fly off of their orbits in a hurry, unless gravity was millions of times faster than light.
The next attempt was made in 1830 by Mossotti, a French physics teacher at the University of Buenos Aires, who had an ingenious idea that electric attraction and repulsion do not balance each other exactly, and the difference is gravity. This idea did not gain much currency until 1900, when Lorentz, Einstein's predecessor in special relativity also, used Maxwell's electrodynamics to show that it did not suffer from Laplace's latency problem, because the correction to force's direction was of the order $v^2/c^2$ rather than $v/c$ as in Laplace's case. That was the consequence of Lorentz invariance compensating the effects of retardation in the first order, as Poincare pointed out in 1905, and an indication that a relativistic theory with gravity propagating at the same speed as light was viable. However, Lorentz's theory did not predict the correct value for the anomalous precession of Mercury. Lorentz's theory was also mentioned by Poincare in 1908, soon after Einstein got interested in extending relativity to gravity.
The author most commonly mentioned as Einstein's "predecessor" is Gerber, who in 1898 inserted into Newton's potential a velocity dependent term that does produce the correct value of Mercury's precession. Gerber's theory was ad hoc however, and he could not explain how his particular correction can be physically implemented. Einstein was aware of Gerber's gravity, it was mentioned in books of Mach and Poincare, but there was not much there to influence him, except perhaps for suggesting the idea that the precession was relativistic in origin. His work was however used by Einstein's detractors to accuse him of plagiarism, and to argue against awarding him a Nobel prize for general relativity. See Gerber's Gravity for details. I am leaving out Heaviside's 1893 theory, which mimicked Maxwell's electrodynamics for gravity and is essentially equivalent to a modern approximation of general relativity, gravitoelectromagnetism, because there is no evidence that Einstein was aware of it.
General metrics were of course introduced by Riemann in his famous lecture, and by 1900 Riemannian geometry was systematized using tensor calculus developed by Ricci and Levi-Civita. Einstein learned of them from Grossman, who was a geometer, and providing the most important mathematical tool used in general relativity. The original version of relativistic gravity theory, called Entwurf, was originally worked out by Einstein and Grossman in 1913. But alas, just like Lorentz's it did not predict Mercury's precession correctly. In 1912 Mie, and in 1913 Nordstrom suggested relativistic gravity theories alternative to general relativity finalized by Einstein in 1916.
Renn and Schemmel's Theories of Gravitation in the Twilight of Classical Physics gives a broad historical overview, see David Darling's Encyclopedia for a nice popular account. A cranky but well referenced account of some lesser known 19th century developments is Hecht's Suppressed Electrodynamics of Ampère-Gauss-Weber. Earman and Glymour's Lost in the Tensors focuses on the mathematical side of history of general relativity.
You can read more on the final stages of its creation in Kevin Brown's Conquering the Perihelion and MacTutor History. See also related What attracted Einstein to the anomalous precession of Mercury? thread. A good book is Renn's The Genesis of General Relativity.