It's always been trivially easy to replace lead in car gas if you don't care about cost. There are a thousand chemicals that will increase octane levels and prevent knocking, and some of them can be bought at your local hardware store.

But none of them were as cheap as tetraethyl lead in the early 20th century, so TEL won.

(This argument doesn't apply to avgas, where TEL did/does more than just prevent knocking.)