Between December 1937 and September 1939
Tolkien's son Christopher has written extensively about the writing of The Lord of the Rings in volumes 6-8 of The History of Middle-Earth. While he presents many different drafts of the text, he doesn't always give them a date (he may not always have been able to date them.
However, I think we can place the writing of the Ring-verse somewhere between December 1937 (when Tolkien began writing a sequel to The Hobbit) and September 1939 (when World War II began - the quote in the question makes clear the *The Shadow of the past was written before the outbreak of the war).
The original written starting-point of The Lord of the Rings - its 'first germ', as my father scribbled on the text long after - has been preserved: a manuscript of five pages entitled A long-expected party. I think that it must have been to this (rather than to a second, unfinished, draft that soon followed it) that my father referred when on 19 December 1937 he wrote to Charles Furth at Allen and Unwin: 'I have written the first chapter of a new story about Hobbits - "A long expected party".'
The History of Middle-Earth Volume VI, Chapter 1: A long-expected party
It is unlikely that the Ring-verse had been composed earlier than this as Tolkien had not yet settled on the idea of Bilbo's Ring being the Ruling Ring.
In this first phase of writing, Bilbo's ring was not the Ruling Ring, but simply the last ring that "the Lord" had not yet retrieved
... till at last he had gathered all into his hands again that had not been destroyed by fire - all save one.
'It fell from the hand of an elf as he swam across a river; and it betrayed him, for he was flying from pursuit ...
The History of Middle-Earth Volume VI, Chapter 3: Of Gollum and the Ring
The first draft of what would become the second chapter of The Lord of the Rings was written during the second phase of writing.
A Chapter titled 'II: Ancient History', precursor of 'The Shadow of the Past' in FR, was now introduced to follow 'A Long-expected Party'. It is of central importance in the evolution of The Lord of the Rings: for it was here that there emerged in the actual narrative the concept of the Ruling Ring.
The History of Middle-Earth Volume VI, Chapter 15: Ancient History
The chapter quoted above also includes the early draft that contains the text of the Ring-verse and an image of the manuscript that contains it.
