Довольно сложный вопрос, зависит от того, что именно считать началом спора. Известно, что обвинения в безбожии звучали уже в античном мире, задолго до возникновения христианства и ислама. Полулегендарный учитель Парменида по имени Ксенофан критиковал традиционную греческую религию за ее антропоморфизм, утверждая, что "если бы у лошадей и быков были бы боги, то это были бы боги-лошади и боги-быки". Он не был атеистом в прямом смысле слова, но его представление о богах довольно сильно отличалось от общепринятого в Греции. Сократа тоже обвиняли в безбожии, хотя это и, судя по всему, не было правдой. Не меньшими критиками традиционной религии были Платон, Аристотель или, скажем, Эпикур. Аргументы, например, Эпикура о невозможности совместить благость и всемогущество Бога используют в том числе и современные атеисты. Если этих ребят считать атеистами, тогда, пожалуй, спор начался с них.
С другой стороны, привычные нам аргументы в пользу существования Бога (иудейского, христианского или мусульманского) - это продукт мысли средневековых философов, таких как Ансельм Кентерберийский, ибн Рушд (Аверроэс) или Фома Аквинский. Ясное дело, все они были верующими людьми и придумывали аргументы для обоснования своей веры. И эти аргументы были направлены напрямую на обоснование трансцендентного Бога христиан и мусульман (хотя при этом использовались логические приемы, придуманные язычником Аристотелем). Получается, тогда начали спор теисты.
А вообще, это бессмысленный вопрос, в стиле "курицы или яйца". По большому счету, разумеется, атеизм никак не мог появиться раньше теизма, именно потому, что атеизму необходимо же что-то отрицать, правильно? Атеизм - это реакция на теистическое мировоззрение. Другой вопрос, что эта реакция может быть очень различной: от простого отрицания-неприятия до создания целостных мировоззренческих систем, построенных на объяснении и обосновании этого отрицания. Так атеизм Дидро сильно отличается от атеизма Маркса, который, в свою очередь, сильно отличается от атеизма Ницше.