The Apostle Paul lived in the Roman Empire. In the Roman Empire, a hierarchy existed 
between Rome and the nations. In English Bibles, the Greek word for “nations” is almost always translated as “Gentiles”. This enforces a hierarchy between Judean people and non-Judean people. While Paul certainly saw a difference between Judeans and others, Rome did not. Rome saw the Palestinian region as another place needing the “gospel” of the Son of the God, the Caesar. The Judeans needed a “savior” who would bring “peace”. Rome accomplished this by enslaving the people, instituting brutal policies against dissenters, and propping up an incredibly unjust dynasty, the Herods.
Saul, the Pharisee, drew heavily on the apocalyptic tradition to enunciate G-d’s power over the empire occupying the Holy Land. He believed Yhwh would raise from the dead those who properly obeyed Torah in order to resist the Roman imperial program. After the apocalyptic experience with the risen Jesus that transformed Saul to Paul, he renounced his Pharisaic station and joined the Jesus movement. Why? We must work backwards to know.
Paul traveled throughout the empire creating communities that obeyed Jesus rather than the Caesar. They organized themselves based on commitment to Israel’s god revealed in Jesus rather than on their own theistic views. The result of this message was a growing network of people unified in resistance to Rome’s way of power. Rome feared this immensely. It signified people united by something other than Rome’s state control. The Judeans believed their god, Yhwh, actually ruled the entire world. What the followers of Jesus realized was that this belief did not prevent Rome from viewing them as one of the other nations requiring enslavement. Put differently, belief in G-d’s power over the whole world and observance of G-d’s Torah did nothing to drive the Romans out of Palestine. What would?
The resurrection of Jesus showed Paul that the way of Jesus, in stark contrast to proper Torah observers, served as G-d’s way for dealing with Rome. What Torah observance failed to do was stretch resistance to Rome beyond the borders of Judea. What good to other tribes of people were complicated laws and foreign indigenous traditions? Furthermore, adhering to these laws at the exclusion of everyone else played right into the hands of the Romans. By keeping themselves divided through strict indigenous laws, the conquered nations had no hope of effectively resisting Roman dominance. This is why, for Paul, Torah is great but insufficient. It brought knowledge of G-d, but through the hands of the powerful in Judea, it became a way of preventing G-d’s sovereignty. Torah excluded those who shared the same lot as the Judeans did: Roman imperial domination. The apocalypse of Jesus to Saul showed him that if Rome was to rule the whole world, it would take the effort of the whole world under the guidance of the G-d of the whole world revealed in Jesus to undo that imperial might.
Basically, Paul stopped doing what the Romans wanted by perpetuating infighting within his own tribe, and he resisted the age-old phrase, “Do as the Romans do.” I believe a faithful reading of Paul must put him in this light. We must understand Paul as saying, “Don’t do as the Romans do, but imitate Jesus.” Furthermore, this explains why Paul so adamantly forbids forcing non-Judean people from becoming Torah observers. The resistance movement focuses on Jesus not Torah. The oppressed find solidarity in Jesus not in Judean traditions. This leads to Paul’s assertion, “There is no longer Judean or Greek, there is no longer slave or free, there is no longer male and female; for all of you are one in Christ Jesus” (Galatians 3.28). The global solidarity movement against Roman brutality made no discrimination in ethnicity, class, or sex.
I now return to the Roman hierarchical structure in which women are below men, slaves are below “free” people, and all ethnicities are below the Romans. Paul clearly denounces these hierarchies by asserting Jesus’ authority rather than Rome’s. This opens the door for people concerned about Paul’s patriarchy and oppressive tendencies to read the Pauline epistles with fresh eyes. Paul, like Jesus, overturned the accepted norms of power. He empowered the oppressed and became one of them. On the side of the raped woman, Brittania, not the powerful male, Claudius, Paul became the apostle to the nations. Not only were these nations not Judeans, they were also like the Judeans: conquered by Rome. He utilized this common bond between conquered peoples to create a solidarity movement under the Lord Jesus rather than the Lord Caesar.
Great questions arise out of this. If the early Christians were to not do what the Romans did, what were the Romans like? How did Jesus and Paul propose to deal with the Roman occupation in more specific terms? On what principles did they base their message? How did people live out the counter-imperial gospel then? While all good questions that aid in interpretation, they are not necessary for moving forward. What we should be asking is who Rome is now? What do the modern-day Romans do? What would it look like to resist that way of life? How can we help establish global solidarity against empire under the banner of Jesus?
messes of ben 
OK, here’s my issue with this.
The heart of the question, I think, revolves around the Greek word ethne, which, as you note, might be translated as “nations”, “peoples”, or, as most of our Bibles render it, “Gentiles”. How we understand that word depends on the sort of contextual background we put it in. If we take ethne primarily as a Jewish term referring to goyim, Gentiles, non-Jews, than Paul understood himself as the apostle to the non-Jews, spreading an originally Jewish faith among the uncircumcised, the Gentiles, who were traditionally understood as outsiders.
But what you’re arguing, as far as I can tell, is that we should understand the word ethne not in Jewish terms, but in imperial Roman terms. He ethne, then, refers to the many, many different nations whom the Romans conquered during their imperial expansion. Nations like the Galatians, Ephesians, and so on. Paul, then, is an “apostle to the conquered”, and understood his mission as primarily one of building solidarity among the conquered nations under the banner of Christ Jesus in resistance to the Roman occupation.
Certainly part of the difficulty of interpreting Paul is getting his dual Jewish and Roman context right. Paul was a Pharisee, zealous for the laws of his ancestors—yet he was also a Roman citizen, and, we must note, thus had certain privileges and rights under Roman law. So things are tricky. Some terms—Christus and nomos, for example—are imported from Jewish tradition, especially insofar as it had been Hellenized since Alexander the Great. And others—soter and euangelion among them, as you rightly note—are terms which imported from the Greco-Roman political sphere into Paul’s (and really, most of the New Testament’s) theological grid. The question with ethne is discerning how to understand its meaning, given that Romans and Jews alike used the terms to mean quite different things.
Basically I want to push back against understanding of ethne in the way the Romans used it, and argue that the way Paul understood it was the Jewish way—ethne means “the uncircumcised” or “the Gentiles” and not “the nations who have been conquered by Rome”: though obviously there would have been a significant amount of overlap on both sides. A few reasons for this.
One, it’s really hard to read Acts and come out with the conclusion that Paul’s mission was to the conquered nations, instead of to the Gentiles. At the Council of Jerusalem in chapter 15, the whole debate circles around whether or not Gentiles could be accepted into the covenant community as is (that is, without circumcision). There’s no way around seeing ethne as “Gentiles” during the debate. And in verse 12, Paul and Barnabas report all of the miraculous signs God had done through them among, yes, he ethne—which clearly means Gentiles in the verses surround it. It seems most correct to assume that Paul understands himself here as an apostle to the Gentiles, not to the conquered peoples of the Roman Empire.
Another text to look at—one that’s really damning to your case, I think—is Acts 10. This is the report of the first convert to the Jesus movement from among he ethne. Far from being a member of the conquered peoples, this man is a resident of Caesarea—a Roman settlement in Palestine—and is himself a Roman, and what’s more, a captain of the Italian Regiment! It doesn’t really get more Roman than that! Yet here is the first convert from he ethne. Clearly, the term here does NOT mean “the conquered peoples”, but rather, the Gentiles. Romans included.
Now, true, it’s not Paul who’s doing the mission here, it’s Peter. But this is the event that sets off the whole issue around which narrative of Acts revolves and the mission of Paul is recounted—the extension of the gospel to he ethne. Given that an officer in the Roman Army was the first convert, how could he ethne possibly mean “conquered peoples”?
Look as well as Galatians 2. Paul gives his own report of the Jerusalem Council and emphasizes that God had given him “the responsibility of preaching the gospel to he ethne, just as he had given Peter the responsibility of preaching to the Jews.” In Paul’s own writing, here the dichotomy is not between conquerer/conquered but between Jew/Gentile. This text, too, seems to problematize your account of Paul’s mission.
What’s more, look at Paul’s letter to the believers in Rome. The list of people to greet in chapter 16 is full of people with obnoxiously Roman names. Even if you take out the ones whom Paul greets as “fellow Jews”, you have: Ampliatus, Urbanus, Aristobulus, Narcissus, Rufus and his mother, Asyncritus, Philologus, and Nereus. That’s a lot of Romans. Can you really still argue that the term he ethne excludes them from Paul’s mission?
There is quite clearly a failure to understand my argument here. I blame it on my own lack of clarity and my attempts at brevity. I would certainly do a longer exegetical work if I could preach 7 sermons on this topic, but sadly, I cannot (yet). If you want to talk extensively about it during which time I will use much more precise biblical examples, I would love to. However, here’s my shorthand answer.
Paul quite obviously understands himself to be the apostle to the “Gentiles”. That is certainly not up for debate. Galatians 2 obviously identifies this. There is no arguing there, but he is more than that.
My first item of business defending my thesis will be the imprecise use of the word “circumcised”. Circumcision was not and has never been an ethnic identifier exclusive to the Judeans. Contrarily, the Romans saw circumcision as a Judean stereotype, along with curly hair and a list of other physical traits. Thus, by referring to Judeans as “the circumcised” Paul automatically injects himself into the semantic range of Roman ethnic hierarchy. This hierarchy was well known throughout the empire. Rome imprinted their coins with it, they built sculptures of it, and they told epic myths about it. Rome stood at the top; everyone was below them. Saul, a Shammaite Pharisee, hoped to undo Roman occupation. He toured Palestine trying to force Judeans to follow Torah properly so that they might rise up to overthrow their occupiers (see N.T. Wright’s What Saint Paul Really Said). He saw the Judeans as special and privileged since they operated under the true god, the god of Israel, YHWH. Essentially, as a Pharisee, Saul created an ethnic hierarchy with the Judeans on top; he acted like a Roman. What the Romans used to their advantage was this ethnic infighting. As long as Judeans fought each other over who resisted the Roman occupation properly, they could never unify to actually deal with the occupiers! Circumcision functioned as one of these divisors. If the movement to deal with the occupation spread beyond Judea, what would unify people who participated in it? Circumcision and Torah clearly were insufficient in Judea. Why would they work better if they spread elsewhere? Thus Paul in Galatians 5, “Listen! I, Paul, am telling you that if you let yourselves be circumcised, Christ will be of no benefit to you…But my friends, why am I still being persecuted if I am still preaching circumcision? In that case the offense of the cross has been removed” (vv. 2 & 11). What did the Romans care if a Judean man was creating religious proselytes? What did the Judeans care if he was making more “circumcised”? Paul’s question is very telling. Christ is of no benefit to the newly circumcised people but apparently is enough to get you in trouble with the authorities! The people in charge seem to be upset with him for something, and it’s not because he is spreading a Roman stereotype of Judean people.
Of course, this elicits the question, what were the authorities so upset about? Which begs an even bigger question, what were the authorities prone to get upset about? An empire that spread the ideology that its people were superior to all others would probably become upset by a man telling people they are equals because of the true Lord (kyrios), Jesus. What you must keep in mind is that this is not a resistance movement akin to Paul’s Pharisaic days. This resistance movement brings the lowly up and the haughty down. It resists ethnic hierarchies! Such an egalitarian movement still threatens the powers that be just not in the way a sword does. So, of course, Roman people could and did join the movement, but at what cost did they join? Circumcision? Torah? No, allegiance! They had to stop following the Caesar as soter, kyrios, and euangelizmo, and follow Jesus instead. That is why at the Jerusalem council in Acts 15 they decided what they decided. Could this global solidarity movement still worship idols and live the sexually immoral lives the Romans lived? Absolutely not! Those were signs of allegiance the Caesar and the hegemonic cultural degradation brought on by the imperialist regime. Would circumcision identify anyone as resisting Rome? No. Keep in mind that millions of U.S. citizens hate the U.S. empire, but most of them refuse to renounce their allegiance to it! The Roman military leader who joined the struggle of the oppressed only solidifies my argument: according to Paul, following Jesus meant severing your allegiance to the imperial powers. This makes it a resistance movement! Where does Paul go to instigate this movement? The people conquered by Rome. What did the Romans call these people? He ethne. These people were obviously not Judeans; so of course his mission is to the “non-Judeans”, but that does not negate the corollary side of that term. I hope that clears at least something up. Maybe?