Another use, specifically as in the Heimskringla in connection with idolatry, is also quite early however. As Jason Fisher pointed out, in the translation of Deuteronomy 28:36 by Ælfric of Eynsham, we read, ᵹe þeouiað fremdum godum, stoccum and stanum, ‘thou shalt serve other gods, stock and stone’. In this verse, the KJV has ‘wood and stone’, but uses ‘stock and stone’ in similar contexts in Jeremiah 3:9 (‘And it came to passe thorow the lightnes of her whoredome, that shee defiled the land, and committed adultery with stones and with stockes’) and Wisdom of Solomon 14:21 (‘And this was an occasion to deceiue the world: for men seruing either calamitie or tyrannie, did ascribe vnto stones, and stockes, the incommunicable Name’). Mr Fisher points out the Hebrew phrase in Deuteronomy is otz u•abn, which Kevin transliterates in his comment below as etz wa-aben (a comment I highly recommend for some historical information on the worship of ‘stocks and stones’ in the Old Testament). However, the latter adds that the wording in Jeremiah uses a definite article, indicating abstraction, so it becomes, et-ha-aben wa-et-ha-etz. Wisdom of Solomon, of course, is only in Greek, so the wording is λίθοις καὶ ξύλοις. So basically, it seems to me, any of these could just as well be translated ‘stock and stone’.
On the subject of translations, I discovered that Tolkien, who—as we saw—echoed the same poet’s Pearl with cognate terms in The Lord of the Rings, actually avoided a cognate in his translation of Sir Orfeo in order to use the ‘stock and stone’ pair. Where line 346 in the original has ‘He no spard noither stub no ston’, Tolkien has, ‘for stock nor stone he stayed his tread’ (Sir Gawain & the Green Knight, Pearl, and Sir Orfeo, trans. J.R.R. Tolkien [NY: Ballantine, 1980], p. 142). Clearly, the phrase is a favourite of Tolkien’s!
It is not merely in biblical contexts, however, that the phrase is used in reference to idolatry. In the mid-14th-c. Troilus and Criseyde III.589-90, Chaucer writes, ‘He swor hire yis, by stokkes and by stones, / And by the goddes that in hevene dwelle’ (The Works of Geoffrey Chaucer, 2nd ed., ed. F.N. Robinson [Boston: Houghton Mifflin, 1961], p. 427). In the 13th-c. Laȝamon’s Brut, l. 626, on the other hand, the pair—while connected in meaning—has nothing to do with idolatry. In the description of King Pandrasus’s assault on Brutus’s ‘castle’, we read, Mid stocken & mid stanen stal fiht heo makeden [this is the text in MS. Cott. Calig. A. IX), ‘[W] ith stocks and with stones they made fierce conflict’ (Laȝamons Brut, or Chronicle of Britain; A Poetical Semi-Saxon Paraphrase of the Brut of Wace, Vol. 1, ed. and trans. Sir Frederic Madden, K.H. [London: Society of Antiquaries of London, 1847], p. 27).
Interestingly, the OED also cites John Lydgate’s 1407 work, Reson and Sensuallyte 6411, where we find the line ‘As deffe as stok or ston’. Although Lydgate is not referring specifically to idolatry, one is easily reminded of Psalm 135:15-18 (KJV):
The idoles of the heathen are silver and gold: the worke of mens hands.
They have mouths, but they speake not: eyes have they, but they see not:
They have eares, but they heare not: neither is there any breath in their mouthes.
They that make them are like unto them: so is every one that trusteth in them.
In conclusion, here are some lovely photos of a group of people in modern-day Russia to whom these words would apply.