Saul of Tarsus(Paul), a Jew, was also a Roman citizen, and as I understand it, that was a special status ensuring no matter what, you don’t mess with a citizen or you might have a Roman legion at your doorstep.** How did Saul attain that status and if not known, were there some particular deeds or behaviors that Rome recognized for citizenship? Also, did Saul carry a piece of paper with his name on it?**
Plenty of subjects of the Empire were granted Roman citizenship even if they were of foreign birth and/or breeding; take a look at this site for some more details. In particular, it notes:
Awards of citizenship were not so much a rare reward for outstandingly admirable behavior as a shrewd tool of statecraft. After all, if you go on adding to your population by leaps and bounds every time you conquer a new chunk of land, you don’t want to end up with a tiny nucleus of free citizens who are the “real” Romans surrounded by a disgruntled mass of defeated foreigners. Expanding citizenship was a way to increase the pool of stakeholders who identified with the political leaders of the empire. Sometimes citizenship was granted to individuals and sometimes to whole communities, and I believe it was always heritable. I don’t know the details of how some ancestor of Paul’s gained citizenship (he was born a citizen), but I doubt he had to carry his papers with him.