You underestimate one major factor that afflicts many governments when it comes to these kinds of sweeping laws.
Apathy.
Why would they give people Roman citizenship? If you are a trying to pass a law to make everyone in the Empire a citizen you need to sell it to people whose interests you are going up against. Nations with two (or more) tiers of citizenry have existed for millennia and still do to this day.
Are Palestinians awarded the same legal protection as Israelis? Is it still bad for your karma to be in contact with the Untouchables in India? 30 years ago were black Africans given the same rights as the Afrikaaners in South Africa?
Legal systems based on oppression have little desire to change unless pressure is exerted on them from other sources either from above or internationally. There is no Emperor whose word is law in this case and no international community to condemn the practices of the Senate and People of Rome.
So why change anything? Why give the people you conquered a say in your government?
They are your subjects not your citizens.
Roman Government may have been Republican but it was still an Imperial Power. There is not going to be a sudden desire to give everyone the same rights if the system has become entrenched in the abuse of its subjects and rewarding its citizens.
What point is there given legal protection to people you can take money from freely and who have no avenue of complaint in your government. They have no voice why should listen to them? Let them run their own authorities at a local level but you will always have the last say in who rules as Pro consul or governors. When they rebel kill them, enslave them and get re-elected as that guy who won the campaign.
Citizenship was rewarded to people throughout the Republic for various personal reasons, but with very constraining legal implications to keep their numbers small (such as ensuring that BOTH parents must be citizens to produce further citizens and given there was very little reason to give a woman Roman citizenship she would have had to be born into a family that were already Roman citizens etc).
But during the Republic they did extend their citizenship. The mere fact that freed slaves become citizens automatically extended the citizen body. The mere fact that a Sabine clan like the Claudians could move his clan to Rome in 504 BC and be enrolled as patricians immediately would indicate that they are open to outsiders. (Even if legend, the mere fact that the Claudian clan had it would indicate that there was no shame on you having non Roman origins even for Roman aristocrats).
First to all of Latium after the Latin War of 338 BC, then to the elected magistrates of the municipalities. Even before that, they gave citizenship to freed slaves, something that nobody, not even Athens, ever did. Any Roman citizen could create citizens by the expedient of buying slaves and freeing them! And many did so, if only to increase the number of clients and people who would vote for them.
They gave citizenship to Latins who moved to Rome, they gave full citizenship to various Italian municipalities, like Arpinum, Formiae, and Fundi in 188 BC, and others too like the lowland Sabines in 268 BC.
Then they invented half citizenship as a midway step to full citizenship, for even more people.
And during the late Republic, men like Marius and Cicero, from Arpinum, which only gained citizenship in 188 BC, were elected consuls. So did Pompeius Strabo and his son, from Picenum.
Then there is the Social War. The fact that they gave in eventually to the Allies' demand tells us that there was already a sizeable portion of the Roman citizens who were in favor of giving citizenship to the Italians, like Drusus, if only to give them large clientage to vote for them in elections.
Then there is the fact that Latins and allies could form part of citizen colonies, and in doing so, became full citizens if they left the colony and moved to Rome.
And many many more.
Compare Rome to the citizenship policy of Athens, or Sparta.
To answer the thread, yes they could gradually extend citizenship in a continuing Roman Republic. First is to give citizenship to retiring auxiliaries as a cheap method of payment. That would ensure the growth of Roman citizens in Frontier areas. Then settle citizen legionnaires among the provinces to further buff the numbers. Then create more citizen colonies in the provinces, and give citizenship to children of Roman fathers and native mothers, like was already done during the second century BC.
Then give citizenship to all elected magistrates of cities, and extend this to tribal leaders, like what was already done during the Republic. That would give the citizenship to provincial aristocracies, who would be clients of various Roman senators.
And give citizenship to people who would directly purchase it like what happened in real life.
Then enslave en masse the rebels, or prisoners of wars during its conquest, sell those slaves to Roman citizens, and when they or their descendants become free, they would be citizens.
By the second and third century, there would be so many Roman citizens in the provinces, that it would be easy to give them en bloc. First to Southern Gaul, Mediterrean Spain, etc.
All of the above would simply be an extension of trends that happened during the Roman Republic. Citizenship would go from Rome, to Latium, to Central Italy, to all Italy south of the Po, to Cisalpine Gaul, to Narbonese Gaul, Sicily, etc, if not form official state action, then from migration, establishment of colonies, granting of citizenship to elected magistrates, retiring from auxiliary regiments, freeing of slaves, enlisting as legionnaires (non citizens who enlisted in the legions would automatically be given citizenship to keep the legions 100% citizen), purchasing citizenship from corrupt officials, and other methods.
It won't really affect politics in Rome, since a voter need to be actually in Rome to exercise his franchise.