There is a teaching that Jews have bechira chofshis, and only as regards their performance of mitzvot. (I don't have a source for the first claim offhand; please help. The source for the second claim may be the Pirkei Avot that everything is in the hands of Heaven except the fear of Heaven.)
Do the umos ha'olam have bechira chofshis as regards their performance of their mitzvot? Or is it a different story?
The answer is Yes, but some background first:
Judaism has no clear tradition regarding the non-Jews. The Rabbis usually extrapolate on them either from the Jews or from the animal and non-animal nature (see for example "Lessons from the rock" question).
The term "free choice" is also very vague philosophically, psychologically and neurologically. E.g accepting a true free-choice means there's something Hashem's not controlling. Therefore talking about the free-will we need to define the behaviors and scenarios that will reflect whether it is the FW or not so we all can be on the same page. (just a note)
A simple rule I use about non-Jews is that all the general sayings of our Sages (including all the Avos Mishnah) apply only to the Jews and cannot be extrapolated on the non-Jews unless explicitly mentioned so.
To your question, I would use two ways of "proving" that they do have certain FW:
As the aforementioned question about non-animated nature shows that the Sages see the Nature as serving Hashem willingly, also see Rambam's Yesodey Hatorah 1, we can conclude that the non-Jews have the FW as they are not less than nature.
The very idea of commandments assumes that the subject has a choice between doing and not-doing as commanded. One can not be commanded to perform a behavior he's forced to and that invalidates the idea of reward and punishment.
THe Yerushalmi (Kiddushin 20a) on Dama Ben Netina's heroic honoring of his parents says that hence the proof that Hashem does not hold the reward of the Gentiles (also):
"א"ר שבתי כתיב (איוב לז) ומשפט ורב צדקה לא יענה אין הקב"ה משהא מתן שכרה של עושה מצות בגוים"
A similar conclusion here in Bavli (B"K 38). This adds-up to other numerous examples when the Gemmorah says that X (Bilam, Navudnazzar, numerous kings) was rewarded by Hashem for doing good deeds.
I am unaware of a teaching that says only Jews have Bechira Chofshis, or that such bechira would only apply to mitzvos.
Please consider: "Rebbe [Yehuda HaNasi] said: Which is the straight path that a person should choose for himself? Whichever [path] that is [itself] praiseworthy for the person adopting [it], And praiseworthy to him from [other] people. And be as careful with a light commandment as with a weighty one, for you do not know the reward given [for the fulfillment] of [the respective] commandments."
(Pirkei Avos 2:1)
What point would Rebbe be making here if people lacked free will? Who is he advising on which career to choose or which mitzvah to be careful with?
Tanach verses:
Deut 30:19 "This day, I call upon the heaven and the earth as witnesses [that I have warned] you: I have set before you life and death, the blessing and the curse. You shall choose life, so that you and your offspring will live;.."
Here near the end of the Torah, we are told that we should choose life over death. Hence we must have free choice.
Isaiah 7:15 "For, when the lad does not yet know to reject bad and choose good, the land whose two kings you dread, shall be abandoned."
There is an age when a youth starts to be able to exercise choice.
Gen. 4:7 "Is it not so that if you improve, it will be forgiven you? If you do not improve, however, at the entrance, sin is lying, and to you is its longing, but you can rule over it."
Here, Cain, (a Gentile, since there were no Jews then) is told he has free choice in the matter of sin.
Isaiah 56:6 "..And the foreigners who join with the Lord to serve Him and to love the name of the Lord, to be His servants,.."
Here Gentiles are described by the Prophet as "joining, serving, and loving." These are things one cannot usually be described to be doing against one's own free will if done in "love".
Deut. 23: 16-17 "You shall not deliver a slave to his master if he seeks refuge. [Rather,] he shall [be allowed to] reside among you, wherever he chooses within any of your cities, where it is good for him. You shall not oppress him."
Here we see that when a Gentile slave escapes his master and seeks refuge with the Jews, we are to grant sanctuary. Part of the grant is that the Gentile may choose where he wishes to settle. (The Hebrew words used are " אֲשֶׁר־יִבְחַ֛ר ".) That is the root verb for "bechirah" or "choice".
So we see that even in secular matters (not just commandments) a Gentile has a choice.
It seems all (Jews and Gentiles) have free choice in both secular and religious matters.
As far as the quote: "Everything is in the hands of Heaven except the fear of Heaven."
It is not to be found in Pirkei Avos. It is to be found in Talmud Brachos 33b:
"And Rabbi CḤanina said: Everything is in the hands of Heaven, except for fear of Heaven."as it is stated: “And now Israel, what does the L-rd your G-d ask of you other than to fear the L-rd your G-d, ... [to walk in all of His ways, to love Him and to serve the L-rd your G-d with all your heart and with all your soul” (Deuteronomy 10:12).]
The statement means that all things in life may be fully granted by Heaven, except fear of heaven which is a up to a person's free choice; to listen to Hashem. R' CHanina seems to learn this from the structure of the verse: "..what does the L-rd your G-d ask of you other than..". So, fear of Heaven is the only thing possible that Hashem would need to ask of us, because everything else is solely up to Him. Yet if he does need to ask us for it, then He must have given us free choice.
It seems from all of the above that the verses of Torah themselves and the words of our Mishnah and Talmud, (quoted above) logically are self evident proofs that all men (Jew or Gentile) have free will to choose in secular and religious matters.
I mean you can read them on their face and you should come to that conclusion.
However, if you need a proof from a Rabbinical source that agrees, you should read the Rambam Hilchos Teshuvah ch.5 . I have provided some excerpts of it below.
"Free will is granted to all men. If one desires to turn himself to the path of good and be righteous, the choice is his. Should he desire to turn to the path of evil and be wicked, the choice is his.
This is [the intent of] the Torah's statement (Genesis 3:22): "Behold, man has become unique as ourselves, knowing good and evil," i.e., the human species became singular in the world with no other species resembling it in the following quality: that man can, on his own initiative, with his knowledge and thought, know good and evil, and do what he desires. There is no one who can prevent him from doing good or bad.
A person should not entertain the thesis held by the fools among the gentiles and the majority of the undeveloped among Israel that, at the time of a man's creation, The Holy One, blessed be He, decrees whether he will be righteous or wicked.
This is untrue. Each person is fit to be righteous like Moses, our teacher, or wicked, like Jeroboam. [Similarly,] he may be wise or foolish, merciful or cruel, miserly or generous, or [acquire] any other character traits. There is no one who compels him, sentences him, or leads him towards either of these two paths. Rather, he, on his own initiative and decision, tends to the path he chooses.
This was [implied by the prophet,] Jeremiah who stated [Eichah 3:38: "From the mouth of the Most High, neither evil or good come forth." Accordingly, it is the sinner, himself, who causes his own loss.
This principle is a fundamental concept and a pillar [on which rests the totality] of the Torah and mitzvot as [Deuteronomy 30:15] states: "Behold, I have set before you today life [and good, death and evil]." Similarly, [Deuteronomy 11:26] states, "Behold, I have set before you today [the blessing and the curse]," implying that the choice is in your hands.
Any one of the deeds of men which a person desires to do, he may, whether good or evil. Therefore, [Deuteronomy 5:26] states:
"If only their hearts would always remain this way." From this, we can infer that the Creator does not compel or decree that people should do either good or bad. Rather, everything is left to their [own choice]."
