You probably gain your first level, but that doesn't mean you can use this
The rules for creating characters mention "gaining a level" in the Beyond first level section (emphasis mine):
Beyond 1st Level
As your character goes on adventures and overcomes challenges, he or she gains experience, represented by experience points. A character who reaches a specified experience point total advances in capability. This advancement is called gaining a level.
Note that this is descriptive, not proscriptive: it says that when you obtain levels beyond the first it is called "gaining a level", but it does not say that obtaining the first level is not called "gaining a level". It does say that "gaining a level" is synonymous with the advancement in ability signified by a specified experience point total. It does not say that this new experience point total cannot be "0" (and see cavaliers below) nor that the capabilities gained cannot be those of first level.
Even though you likely begin playing at 1st level, the narrative of the game assumes that you character had a life before this point in time: that is your Background:
Every story has a beginning. Your character’s background reveals where you came from, how you became an adventurer, and your place in the world.
So your character had a life before they were first level or had a class, and at some point they became first level in their class. The process of going from 'not having a level' to 'being first level' has to be called something, and "gaining a level" seems a pretty natural fit; certainly the rules don't suggest something else for it.
Indeed, for a multiclassing character, going from not having a level in a class to having one is explicitly called "gaining a level":
With this rule, you have the option of gaining a level in a new class whenever you advance in level, instead of gaining a level in your current class.
Here "gaining a level" is used interchangeably for obtaining a further level in your current class or your first level in your new class. Arguing that a single-classed character did not "gain a level" when they become first is special pleading - to be convincing, you need to explain why it would not simply be called "gaining a level".
Sdjz, in their answer to this question, suggests one reason why "gaining" your first level would be problematic. As a wizard, you "can add two wizard spells of your choice to your spellbook for free" each time "you gain a wizard level." Sdjz argues that if this applied at first level, it then would give wizards more than the six starting spells the class is supposed to have. However, I believe this is an example of specific over general. The general rule allows wizards to add two spells per level, but this is superseded by the specific rule that says (emphasis mine) "At 1st level, you have a spellbook containing six 1st-level wizard spells of your choice." The hard limit of six spells at the start applies, regardless of whether or not you "gained" first level. It is this hard limit, in fact, which keeps a character that multiclassed to wizard from starting with more than six spells, even though in this case we know that they did gain first level.
Finally, while 5e currently starts play at level 1, as a historical note I would mention that not all editions did this. In AD&D 1.5, cavaliers (and their sub-class paladins) started at negative experience points and had to adventure to eventually gain first level. In the Greyhawk Adventures Hardback (which was a bridge product between first and second editions), optional rules for making a 0th level, classless character were introduced. That character could spontaneously manifest abilities of multiple different classes, and when they eventually became first level they finally selected their class. While we don't know what the upcoming revision to 5e will bring, optional rules for 0-level characters "gaining first level" in a single class would not require changing any of the current language.
Thus, while we cannot say that RAW admit that single class characters gain first level, we can say confidently that nothing says they don't, multiclass characters explicitly do, no problems with this wording have been suggested, and it certainly seems like a natural use of the language.
So what about Divine Souls?
The point of the original question was whether saying that characters gained their first level would permit an exploit by which a single-classed sorcerer could immediately gain a cleric spell upon character creation, because of the specific language in the Sorcerer Spellcasting feature.
If we grant that a character gains a level when it becomes first level, is this permitted? Let's look carefully (emphases mine):
Additionally, when you gain a level in this class, you can choose one of the sorcerer spells you know and replace it with another spell from the sorcerer spell list, which also must be of a level for which you have spell slots.
Now the question becomes, if a character gains a level as a sorcerer, do they know sorcerer spells and have sorcerer spell slots? If they are gaining second or higher level, they already know sorcerer spells and already have sorcerer spell slots. But do they know these spells and have these slots when they gain first level (whether single classes or multiclassing into sorcerer)? That is not clear.
The rules do not address becoming first level, but assume that you have been first level for some unspecified time when you begin play. Within the fictitious game narrative, was a character initiated as first level, and as a result was then able to learn spells before their first adventure? Or did they slowly learn spells as an apprentice, and once they had mastered a few of them they then became first level? Or did all of the abilities gained at first level suddenly become available at once, at the same time they gained first level? The rules do not address this, because whatever the process was, it already happened before play starts.
Because the rules do not address this, the DM is free to structure the narrative in any way that suits their world-building. If they decide to allow the exploit, they can say that yes, the apprentice sorcerer already has spells and spell slots when they finally become first level and are then able to switch one out. If they don't wish to permit this, they can say that no, gaining first level is merely the beginning and that from that point on the sorcerer works to learn spells until their adventuring career starts.
Thus, while it seems like a character does "gain first level", that in no way decides whether or not to allow this exploit.