There are a few exceptions
The game does not exactly define What is a living creature?, but answers that this stack came up with are things like living creatures are: (1) creatures that have a soul, in which case the answer here would be yes, or (2) creatures that have a metabolism (and thus normally need to eat, drink, and breathe to sustain themselves), in which case not all of them would necessarily need to have a soul.
By formal logic, statements like "if a living creature dies, its soul departs its body", or "any mortal creature that breaks such a contract instantly forfeits its soul" do not strictly mean a living or mortal creature must have a soul. For that to be true you need an antecedent statement, which is only implied here, namely "Every living/mortal creature has a soul". As @encryptor stated in a comment, this situation is like the statement "when a person dies, their heritage goes to their heirs" which doesn't mean that everybody has a heritage and heirs.
The rules, however, are neither a treatise on formal logic nor a legal text, and I think that for practical purposes @QuadraticWizard's answer is correct here; living creatures (however you identify them) normally have a soul, and everything beyond that is an exception or corner case, and would need the DM to adjudicate. Here are some of these:
Genies
One such exception are Genies. They are elementals, so neither constructs nor undead. Their lore states:
A genie is born when the soul of a sentient living creature melds with the primordial matter of an elemental plane. Only under rare circumstances does such an elemental-infused soul coalesce into a manifest form and create a genie.
Thus genies do not have a soul, they are a soul, coalesced into manifest form.
Barovians
Another more straightforward example are the Barovians. The Curse of Strahd states (p. 10):
Barovians are made of flesh and blood. They are born, they live, they age, and they die. But not all of them - only about one in every ten - have souls.
PS: creature types are just a label upon which to hang other rules. Your example of the Nabassu shows well how that works -- there is no general rule that constructs do not have souls, but the Nabassu can use the creature type, in this case to declare that a construct does not have a soul that the Nabassu can eat.