The problem is that in faerun, being godless has serious repercussions and almost all magic comes from gods.
This is not quite correct.... there's a bit more nuance to that, if we don't want to be misleading.
Being Faithless, such as would end up up in the Wall of the Faithless, is something more specific than just 'not being devout'. It's not something you just end up with by accident - it's deliberate; paying empty lipservice to gods deceitfully, or actively foreswearing or renouncing the gods in general are the sorts of things that will do it... but just generally not following any particular deity will not. The folks of the Forgotten Realms (Faerun is a continent, on the world of Toril) know that the gods are real and extant, in the same way that we know air and water are - they're right there, and the effects of their power are highly visible - no-one (or very few people) 'do not believe' in them. Most people do not
follow a particular deity, however - they know they exist, and they often offer small prayers or offerings to
various deities that match the task they're pursuing - farmers will often visit shrines to Chauntea in the hopes of a good harvest, for example, while Norland sailors might ask Valkur for good winds... of if they're feeling fearful, make an offering to Umberlee to stave off ill fortune at sea... but they are not followers of these deities, in most cases, and that's okay.
Magic comes from manipulating and drawing power from the weave, and there are a multitude of ways that mortals tap it - some use divine intermediaries, who draw from the weave and channel that to their followers in controlled ways, handling all the tricky parts of manipulating powerful magic so their clerics and paladins don't need to know how to. Others do so without an intermediary, and must perform the complex task of drawing power from the weave and forming it into something that can be actualised, without burning themselves to a cinder, on their own, through many long yeas of dedicated study. Some have this connection whether they want it or not, and have to learn to wrangle it by intuition and force of will, lest it destroy them or hurt people close to them, because when you have an always-on connection, you can't just turn it off, at least not for long.
Either way, however, magic does not come from Deities as the source; it comes from the weave (or more properly, it comes from the raw magic which is the force-like essence of everything, everywhere, which is mostly untappable, and for which the weave itself acts as the filter-cloth between it and most spellcasters - sorcerers excepted, interestingly enough), and in the case of those who do use a divine intermediary, it comes to them drawn from the weave by that intermediary, managed and then channelled down to them in pre-packaged forms. A light-domain cleric who casts fireball doesn't know how to arrange the weave to evoke a fireball, nor the method of doing so - unlike a wizard who must know both of these things with exacting precision - what the cleric knows is the proper means to request that power of their intermediary, and how to access and direct it when it is granted to them through their divine connection. However, both of these individuals are causing the same manipulation of the weave, at the end of the day. Deities have the power to use, wield and manipulate more of the weave at once than any mortal being could ever really contemplate, and they use this capacity to mediate power to their mortal followers based on how strong a divine connection that follow is able to safely handle (and how much the deity thinks they've a right to, presumably).
The forgotten realms is a perfectly acceptable realm space for glory paladins, theurgist wizards, divine soul sorcerers, zealot barbarians, and all manner of other classes and subclasses that channel varying amounts of divine energy and power without knowing much at all about any deities and certainly not being dedicated followers of them. In the cases of such, when they don't follow a particular deity, they usually draw their power from the weave, by way of a divine folio, independent of the deity or deities that happens to control that or those folios at the time.
