I think the best way to have this happen is to have Rome not exist in the first place. Give Carthage a crushing victory in the Second, or preferably the First Punic War, and throw in Epirus running around Italy. We can have small isolated Greek Colony states like Tarraco, Massilia, and Carthaginians from Spain influence the Celts with Greek Administration. After years and years of influence from Greece, you have an emerging state.
The Greek colonies are not isolated, given their maratime trade connections. And the Celts had already undergone much internal political development up until the First Century BCE. And as I've previously explained, the Gaulish Arverni was at least one example of how the Celts came close to forming a proper state.
Then again, it depends on how one defines a "state". Perhaps the Celtic "tribes" had more in common with the Greek city-state culture than most people think. Both Greeks and Celts had actually expanded far from their original homelands long before their cultural identities developed. Both peoples defined themselves by their city of origin or tribal ancestry before thinking of themselves as "Hellene" or "Celtic", if they even did at all.