Avoda zarah is one of the things prohibited by the Seven Noachide Laws. But what about atheism? I know that the 7 Laws are often taken to include a larger number of halachot from the Torah, so would the prohibition against avoda zarah expand to include kefira as well?
Rav Moshe Feinstein, in a t'shuva about allowing children to say a generic prayer in public school (Orach Chayim II #24), refers to the Ramba"m's statement in Mishne Torah that Adam Harishon was given 6 commandments, including belief in God. No'ach and his descendants later got one more, adding up to 7. They both conclude that not only the negative aspect of believing in God is necessary - i.e. not serving other deities - but also the positive affirmation of His creation and provenance over the world, when circumstances call for it. Rav Moshe also uses the inference from the words of Ramba"m explained in @Yishai's answer.
Given the Rambam's statement:
Anyone who accepts upon himself the fulfillment of these seven mitzvot and is precise in their observance is considered one of 'the pious among the gentiles' and will merit a share in the world to come.
This applies only when he accepts them and fulfills them because the Holy One, blessed be He, commanded them in the Torah and informed us through Moses, our teacher, that Noah's descendants had been commanded to fulfill them previously.
However, if he fulfills them out of intellectual conviction, he is not a resident alien, nor of 'the pious among the gentiles,' nor of their wise men.
It would seem that the answer is no, it is not permitted.
As far as I'm aware, just about every posek assumes that all nations are obligated to believe in God in some way or another. This is stated explicitly by Rav Shmuel ben Hofni Gaon (commentary to Beraishis 34:12), Rabbeinu Nissim Gaon (intro to Talmud), probably the opinion of the Sefer Hachinuch (commandment 417, and Minchas Chinuch there), Maharal (Gevuros Hashem ch. 66, in his comparison between murder and the denial of God), Maharatz Chajes (Kuntres Achron published in the end of Minchas Kanaos), the Chazon Ish (Y.D. 62:20), R. Yaakov Kamenetsky (Emes L'Yaakov Beraishis 8:22), R. Moshe Feinstein (O.C. II:24), R. Reuvain Margolios (Margolios Hayam Sanhedrin 56a #25) and R. Ahron Lichtenstein ("Seven Laws of Noah" pg 78).
Most of the above assume that this is the case either because there needs to be an underlying philosophy behind keeping the seven commandments (see Rambam Hil. Melachim ch. 8), as part of the prohibition of idolatry, or because it is included in the restriction against blasphemy (this is stated explicitly by R. Margolios and R. Lichtenstein).
However, there is, as far as I know, one posek who disagrees: R. Moshe Shternbach. He writes in Teshuvos Vehanhagos 3:264 and 3:317 that non-Jews are not obligated in believing in God, as this is only obligated for (and perhaps the only difference between them and) geirei toshav.