As i see there are several possible interpretations:
1) 9:29: Fight {those who do not believe {in Allah AND AT SAME TIME in the Last Day} AND AT SAME TIME do not consider unlawful what Allah and His Messenger have made unlawful AND AT SAME TIME do not adopt the religion of truth} from those who were given the Scripture until they give the jizyah willingly while they are humbled.
(I have written these using Sahih International translation). The 1st, with "wa" as "AND", seems to me as linguistically more straight. According to this interpretation, muslims should force only part of People of the Book to pay jizya. It looks like compulsion against People of the Book compared to other unbelievers. Does not this interpretation contradict Quran 2:256 ?
2:256: Sahih International: There shall be no compulsion in [acceptance of] the religion. The right course has become clear from the wrong. So whoever disbelieves in Taghut and believes in Allah has grasped the most trustworthy handhold with no break in it. And Allah is Hearing and Knowing.
Then i have seen another interpretation: the jizya is just a compensation for not going to army of islamic state. Are they humbled in that case? I think, they can be thought/regarded as humbled, because they have to obey to Islamic state. In this case, there should not be difference between people of book and other unbelievers. So, we have to make place for other unbelievers in this ayat, and understand last "wa" as "AND TOGETHER WITH WHO ...", and let's similarly understand other "wa"s:
2) 9:29: Fight {those who do not believe {in Allah AND TOGETHER WITH WHO ... (OR) in the Last Day} AND TOGETHER WITH WHO ... (OR) do not consider unlawful what Allah and His Messenger have made unlawful} AND TOGETHER WITH WHO ... (OR) do not adopt the religion of truth from those who were given the Scripture until they give the jizyah willingly while they are humbled.
If we understand "wa" as "AND TOGETHER WITH WHO", then it is doubtful for me, because i think, should not it be better said with "aw", meaning "OR"? And in this case seems there is even more compulsion against non-{People of the Book} compared to 1st interpretation.
The explation "they can be thought/regarded as humbled, because they have to obey to Islamic state" can be used also with 1st interpretation. If do so, why there is comparatively more compulsion to People of the Book? I think, that can be explained with that it is more easy for them to embrace Islam. Also, the word "jizya" is from root of "punishment", so it can be considered fair punishment for them, which they merited in front of God and must pay. Also, who says that non-believers cannot serve in army? - seems nobody, so that was not very good explanation. Is not that punishment to People of the Book a compulsion? Maybe meaning of the word "ikrah" which is used for "compulsion" in 2:256 is only strong compulsion, like with attempt to kill, but compulsion with forcing to pay some money is not counted? It is hard to understand it that way. So, probabaly, it is not counted as compulsion because it is already fair punishment given by God.
I see that the "AND TOGETHER WITH WHO ... (OR)" meaning of "wa" can be used also with 1st interpretation. If "AND AT SAME TIME" is used, then only those people of the Book should be fought who do not do all that things, and whoever of them who does not do only part of them should not be fought, for example, who believe in Allah, of them, should not be fought even if he does not believe to the Last Day, nor consider unlawful what Allah and His Messenger have made unlawful, nor "adopt the religion of truth". Another example: who "adopts the religion of truth", of them, should not be fought even if he does not believe in Allah and does not believe to the Last Day, nor consider unlawful what Allah and His Messenger have made unlawful. This interpretation looks a little strange to me. So, probably, there is the "AND TOGETHER WITH WHO ... (OR)" meaning.
But I have again changed my mind. 2nd way of logical precedense looks more correct to me now, because non-people of the book also can be given punishment from god, and it is also linguistically ok. and if "of people of the book" was appended to all of the listed features, could not it better put before the list? But does not this interpretation contradict with 2:190?
Fight in the way of Allah those who fight you but do not transgress. Indeed. Allah does not like transgressors.
I think both interpretations contradict with it, and also with 2:256, but this interpretation contradicts more. I think I can change my mind again.
Is jizyah, (as it is commonly understood, like tax), compulsion? I think, if it is not too much, it is fair, because muslims also have to make some duties like paying zakat and sadaka, and go to juma prayer, but unbelievers are free from islamic duties in an islamic state or society, so it seems fair if they pay money to muslims or to islamic state to compensate it. The commandment in Quran 9:29 applied to unbelievers outside of muslim countries (states) looks like commandment to make some wars with non-muslim countries (states), but, I think, this should be undrestood only with other ayats which command to abide/fulfill agreements, so it can transform to lawful activities in non-muslim countries with intention to gain more winning, powerful position for muslims, for example, in economy, in politics, for example, to successfully produce and sell some products, advocate muslim rights, and successfully bring up more children, and successfully spread Islam among non-muslims, if figthing is not possible due to agreements.
So, shortly speaking:
How should this ayat be interpreted?
- using text of Sahih International with addition of parentheses:
Fight {those who do not believe in Allah or in the Last Day and who do not consider unlawful what Allah and His Messenger have made unlawful} and {who do not adopt the religion of truth from those who were given the Scripture} - [fight] until they give the jizyah willingly while they are humbled.
But somebody can also understand this way:
Fight {those who do not believe in Allah or in the Last Day and who do not consider unlawful what Allah and His Messenger have made unlawful and who do not adopt the religion of truth} from those who were given the Scripture - [fight] until they give the jizyah willingly while they are humbled.
So, I cannot strictly answer this part of the question with proofs.
Does it mean that Muslims are responsible to physically fight non-believers?
- Yes, but not to fight with intention to physically kill, but only to force to pay jizya. Seems, forcing to pay jizya is with intention to make unbelievers to embrace Islam.
I have remembered another interpretation of 9:29 which removes the contradiction with 2:190, 2:192, 2:193 and 2:256 and 10:99, and 17:33 and 60:8:
3) Whenever you fight {those who fight you from { {those who do not believe in Allah or in the Last Day and who do not consider unlawful what Allah and His Messenger have made unlawful} and {who do not adopt the religion of truth from those who were given the Scripture} }}, stop fighting if they give the jizyah willingly while they are humbled.
I do not feel Arabic very well, and i think that this way of interpretation is possible because the first part, "fight those who ..." maybe theme ie it is already known and it is a reference and the "until they give the jizyah ..." part maybe "rheme" a new information, (or a new commandment), and important part of the sentence. See https://en.wikipedia.org/wiki/Topic_and_comment about theme and rheme.
But the word "khatta" ("until") can be translated as "in order to", so this interpretation is suspicious for me. Also there are other problems with interpretation: the reference part is too long to be just a reference, common meaning of the word "jizya" does not suit this very well.
( I wrote about this interpretation in Russian in http://dinarkurbanov.wp.kukmara-rayon.ru/2010/09/22/komment-k-filmu-islam-cto-doljen-znat-zapad/ and about this way of interpretation in Freedom of belief: How do you reconcile these two? ).
Also a question appears for me, what is jizyah? Is it indeed a tax, that should be paid constantly forever? Also "al" ("the") before it, shows to it. Maybe I will make a new question about this.