Can we focus on this?
Trial and error. And obviously a lot of stuff didn't work. Some apparently did but had problems due to either cost effectiveness or other concerns. I found the original story, although I had to get it from an archive since the original article has been purged.
I also have an issue that many of these articles make no mention of what "octane" is - like it's just some sort of property of the fuel or even the proportion of actual octane in the fuel, and not a chemical that's the reference fuel to compare relative antiknock properties.
web.archive.org
In the laboratories of Charles Kettering, however, the search for a gasoline additive to cure "knock" had been going on for some years prior to Midgley's rediscovery of TEL. In 1911 Kettering had invented the electric self-starter--a landmark development in automotive history that eliminated dangerous hand-cranking and enabled many Americans (particularly women) to drive for the first time, arguably killing steam and electric cars in the process. This invention would make "Boss" Kettering rich, famous and beloved to a nation falling in love with its wheels. Thanks to the starter, the folksy inventor's new firm, Dayton Engineering Laboratories Company, or DELCO, received its first big order, for $10 million, from the upstart General Motors Corporation, founded only three years earlier by William Crapo Durant.
GM's 1912 Cadillac was equipped with DELCO's self-starter and battery ignition. When customers reported that the engine of this luxury automobile had an alarming tendency to knock--a sharp, metallic sound hinting at damage being done inside the engine--critics blamed Kettering's electrical components.
Kettering was convinced, rightly, that knocking was a function of an engine's fuel rather than ignition problems. When Kettering and his partners sold DELCO to Durant's GM and its new partner--Alfred Sloan's Hyatt Roller Bearings--in 1916, his lab was already engaged in a search for the cure. Following the sale, this work was transferred to his new firm, the Dayton Research Laboratories, where a newly hired assistant, Thomas Midgley, was assigned to study the problem of engine knock.
Stabbing in the dark, Midgley got lucky quickly when he added iodine to the fuel, stopping knock in a test engine and establishing for all time that the malady--premature combustion of the fuel/air mixture--was connected to the explosive qualities of the fuel, what would later be called "octane." Iodine raised octane and cured knock; however, it was corrosive and prohibitively expensive. Inspired by the fundamental breakthrough, Midgley nonetheless carried on with fuel research, testing every substance he could find for antiknock properties, "from melted butter and camphor to ethyl acetate and aluminum chloride." Unfortunately, "most of them had no more effect than spitting in the Great Lakes."
This mentioned others that were tried, where iodine was the first that seemed to work. Others worked including aniline, but apparently that stunk up everything so bad that it was determined to be unsuitable.