In this post (link), we discussed R. Norman Lamm's theory that doubt is not considered disbelief, even if it obviously is not ideal. I was informed that a similar approach can be found in R. Avraham Weidenfeld, Lev Avraham (1:142:4), who also quotes the Chazon Ish (Emunah U-Vitachon, ch. 2) who says that those "of little faith" are still considered to have faith. I also found that R. Yehuda Amital adopts this approach.
R. Yehuda Amital, Jewish Values In A Changing World, pp. 178-179:
Rabbi Avraham Yitzchak Kook also struggled with this issue. He maintains (Iggerot Ha-Ra'aya, I, letter 20, pp. 20-21) that, rationally speaking, it is impossible to deny God with absolute certainty; at most, one can cast doubts. A heretic is one who denies God with certainty, and he indeed acts out of evil:
Even though it is absolutely forbidden and an evil sickness even to doubt or question matters of [our] perfect faith, we nevertheless find that Chazal judged as a heretic only one who denies outright, i.e., one who reaches the opposite determination. This antithetical determination cannot possibly be found in Israel in any individual who is not an absolutely wicked man and intentional liar. For even the greatest wickedness can cast doubts only among the weak-minded. He who dares to say that he denies with certainty must be an absolutely wicked man, who is rightfully judged with all the punishments explicitly assigned to him.In light of Rabbi Kook's words, it may be argued that the majority of non-religious people today do not fall into the category of "heretics," for that classification applies only to those who deny God with certainty.
This having been said, we remain with the question of what attitude we should adopt towards those who deny God with certainty.
 The distinction between disbelief based on uncertainty and that based on certainty can be derived from another source as well. The Gemara (Shabbat 31a) brings the famous story of the gentile who came before Hillel in order that he convert him to Judaism. Although the gentile insisted that he was ready to accept the Written Law but not the Oral Law, Hillel agreed to covert him. Rashi struggles with the problem of how this gentile could have been converted. Surely, "If a gentile comes to accept the Torah except for one thing, we do not accept him" (Bekhorot 30b). Rashi, therefore, writes: [Hillel] relied on his wisdom that in the end he would habituate him to accept [the Oral Law], for it is not the same as saying, 'except for one thmg, for he did not deny the Oral Law; rather, he did not believe that it comes from God, and Hillel was sure that, following his instruction, [the gentile] would rely on him." Rashash explains what Rashi says as follows: "The term 'heretic' only applies after exhaustive investigation, but this [gentile] did not investigate nor was he convinced of anything. He simply did not believe. [Hillel] was therefore sure that after he clarified the truth of the matter for him, he would believe."