IIRC, the Sumerians (through the Akkadians perhaps) left records stating they had to build walls around their cities. Which to me certainly implies the Sumerians had cities without walls for some time. Pretty big deal that, to have recorded it.
Cities subjected by some empire or another were sometimes forced to tear down their walls and there were perhaps periods of relative isolation and peacefulness during the founding of some cities where one wasn't immediately necessary, but even very ancient settlements commonly had at least palisades. There are probably some other exceptions; Sparta famously did not have walls under the philosophy that nobody should ever dare even try them, but they were also blessed by geography.