"Carved from the living rock" — since when was rock ever alive?

My understanding of this phrase is that "living rock" refers to rock that is still part of the earth, like a mountain. Contrast this to a rock that has been quarried and moved somewhere; it is still rock, but no longer "living". So rather than building steps out of some material and placing them in a shaft or on a hill, the steps are literally carved into the planet itself.

Another way to look at it is that it's like a tree. You can carve things out of wood, but if you carve a living tree it's different, because the tree is still part of nature.

The phrase living rock itself refers to rock-cut architecture, which is:

the practice of creating buildings and other physical structures by carving natural rock

The Wikipedia article on the Sphinx also mentions the term in context, saying that it is:

rock that was present at the construction site, not harvested and brought from another location

So the fact that the rock was living means that it existed in some place--it was already living in the area that it was used. On Google Books, the phrase appeared by 1794, in *Indian antiquities:

It also was in use in 1785, in Dodsley's annual register:

The Oxford English Dictionary lists several uses of the phrase living rock, under the following definition:

d. transf. (a) In various phrases of biblical origin. Of water: Constantly flowing; also, refreshing. (b) Of coals: Burning, flaming. Cf. live adj.1 2 (c) Of rock, stone: Native; in its native condition and site, as part of the earth's crust.

The first uses of "living" to refer to rock is in the 1600s:

1697 Dryden tr. Virgil Æneis i, in tr. Virgil Wks. 203 In a spacious Cave of living Stone.

The OED writes also that this is related to the now historical definition of live:

a. Of an element (element n. 1): naturally occurring, esp. in an uncombined state; native. Cf. earlier quick adj. 7a. Now hist.

This usage of live was first recorded in 1600. "Living" in the desired sense seems to have derived from this in the intervening years. So this may finally give a date to when this phrase was used: 1697, according to the most recent version of the OED.

Concerning when the phrase entered the language and from where:

The phrase could be a translation carried into English from Latin. In Ovid's Heroides (Letter 6, line 88), Hypsiyle, among her many complaints about Jason's new girl, Medea, claims that she disturbs the natural order. She writes: “Illa loco silvas vivaque saxa movet” or “She [Medea] moves the forests and the living rock.” So while I don't know when it entered, I am guessing that this useful calque came into English some point around the Renaissance. The notion of living rock is at least 2,000 years old then. Does anyone know whether it exists before the Roman Imperial era in Greek or any other Indo-European language?

It could be an allusion to many mythological figures. I know that in Greek, and many other creation stories man is carved from rock or clay. Earth and rocks are supposed to represent life and the idea of a living 'mother Earth'. It's a fairly common archetype in creation myths that life comes from mud, stone, or clay. So the phrase may be referring to rock as living because of how they are life producing so often.