The answer is both and will depend on whether you want a more 'correct' formal register or a more colloquial one.
They becoming his subjects can be analysed as a nominative absolute phrase.
Usually (...) an absolute phrase (also called a nominative absolute)
is a group of words consisting of a noun or pronoun and a participle
as well as any related modifiers. Absolute phrases do not directly
connect to or modify any specific word in the rest of the sentence;
instead, they modify the entire sentence, adding information. They are
always treated as parenthetical elements and are set off from the rest
of the sentence with a comma or a pair of commas (sometimes by a dash
or pair of dashes). Notice that absolute phrases contain a subject
(which is often modified by a participle), but not a true finite verb.
In this sense, the subject of the phrase will be 'they' (in the nominative case).
But in more colloquial English, you will also come across the accusative absolute:
I respected what she said, her being my trusted GP.
Merriam Webster's first definition of the accusative absolute exemplifies the German language. Wikipedia cites ancient Greek, German and Latin. But the second entry at Merriam Webster is the following:
2: a construction in English, especially colloquial English, consisting
of a pronoun in the accusative case joined with a predicate that does
not include a finite verb and otherwise identical with the nominative
absolute (as him being my friend in “him being my friend, I granted