How did Einstein derive general relativity?

His starting point was to realize that Newton's gravity didn't satisfy his principles of the (special) theory of relativity because it wasn't Lorentz-invariant and it included action at a distance, faster-than-light effects of gravity that could spread immediately.

So he was looking for a better theory that would be compatible with the principles of relativity. It took him a decade after special relativity was found to find and complete general relativity. Let me completely skip dead ends he had tried although these stories are interesting and one could learn something from them, too. At some point in 1911, in Prague's Viničná Street (see some letters Einstein wrote about Prague), he realized that the equivalence principle was a very special property of gravity – known already to Galileo but not appreciated as an important principle – and it led his final years.

Eventually he realized that the spacetime had to be curved, by arguments based on the equivalence principle, and it must be described by the Riemannian geometry. He was looking for the right equations that could relate the curvature of spacetime and the density of matter in the spacetime and finally in 1915, he found his Einstein's equations.

I think that he found the equations in their explicit form and the Einstein-Hilbert action from which the equations may be derived via the principle of least action were found later – also independently by Hilbert. We may say that the principle of least action wasn't necessary to discover GR; the equivalence principle was essential but Einstein needed (and one needs) more insights than just this principle.

I highly recommend reading section 17.7, "A Taste of the History of Einstein's Equation", pages 431 through 434 of MTW's Gravitation

(Click the link to read at Google books).

Einstein published a book in 1916 called Relativity which he updated in 1952 just a few years before his death. In chapter 25 he discusses Gaussian coordinates and in chapter 28 he gets to the heart of the matter and states:

The Gauss co-ordinate system has to take the place of the body of reference. The following statement corresponds to the fundamental idea of the general principle of relativity: "All Gaussian co-ordinate systems are essentially equivalent for the formulation of the general laws of nature."

Later then elaborates further:

According to the general theory of relativity,...,by application of arbitrary substitutions of the Gauss variables $x_1, x_2, x_3, x_4,$ the equations must pass over into equations of the same form; for every transformation (not only the Lorentz transformation) corresponds to the transition of the on Gauss co-ordinate system into another.

Which essentially gets to his point. Whatever the variables of spacetime are, any relationship between those variables must be respected even when we arbitrarily change variables. Or in other words, our choice of coordinates is arbitrary as long as we include enough variables to describe the underlying spacetime.

It should be noted in the context of discovery that there is a long standing dispute of priority. However, despite uneducated debate, most scholars agree that Einstein developed special and general relativity largely independently.