While you are waiting for a more detailed response, I can present and link to some other discussions on this topic. Apologies for any spelling or grammar errors I make, I am not a native English speaker. This is also my first post here!

Plebeians were absolutely citizens, and the Patrician-Plebeian divide was a distinction within the ranks of the citizenry (though it mattered less and less over time, and by the Late Republic most Roman politicians were plebeians). If you want to learn more about Patricians and Plebeians there is this thread with answers by u/Alkibiades415 and u/XenophonTheAthenian.

There were several ways to obtain Roman citizenship, especially in the Imperial period when Paul was active. Individuals who had served Rome in some fashion, as well as entire communities, could be granted citizenship. Those who were enslaved and then manumitted by Romans also became citizens. The historian Bret Devereaux, an expert on the military of the Roman Republic, has discussed Roman citizenship in detail on his blog ACOUP, especially the second and third parts of his series "The Queen's Latin". Dr Devereaux explains how it differed from citizenship in other Mediterranean city-states, how it expanded to include Roman allies, how this changed and the citizenry expanded even more in the Imperial period, and how this was viewed both by these newer citizens themselves and by more xenophobic writers.

When it comes to how citizenship was proven, here is an answer by u/Astrogator that should be useful, which also mentions some of the rights afforded to citizens. And if you want to a read more detailed explanation of rights Roman citizens had, here is an older thread answered by u/Celebreth on the topic.

I hope you found this helpful!