The question rests on a severe anachronism, in that many or most ancient cultures in contact with Israelite culture did not have a conceptualization of 'monotheism' or 'henotheism' until well after the biblical books were written. Just to illustrate this, the Greek word 'atheism' was used to describe the Jewish people, because from a Greco-Roman perspective the Jews did not worship the gods of the state religion.1
Within the Hebrew Bible, the family of Hebrew and Aramaic words often translated as 'God' with a capital-G are used for:
- Foreign gods (e.g. gods of Egypt, Baal, Chemosh, Dagon)
- Angels (e.g. Psalm 8.5, where elohim was understood as referring to 'angels' in the LXX, Syriac OT, and NT)
In one case, the spirit of a dead prophet is even perceived as an elohim, despite that the context makes it clear the speaker does not have a deity in mind (1 Samuel 28.13).
Many of the occasions we find 'god' applied to other entities do not deny the existence of such 'gods', only that they were inferior or subordinate to Yahweh.
For example, in Exodus 12.12 Yahweh claims he will 'execute judgment on all the gods of Egypt'. Psalm 82 portrays Yahweh as the chief God sitting in judgment amid a divine council of gods. Yahweh is called 'the God of gods' on more than one occasion, an idiom that simply means 'the greatest God'.2
What this shows is that the common modern definition of the word 'god' — with its connotations of an omnipotent, omniscient, omnipresent supernatural entity — does not correspond very well to the ancient Near Eastern concept of a 'god' as we find that word-family used, at least in the Hebrew scriptures.
The issue to look for, however, is not whether the authors of the biblical books believed in the existence of other gods, but what qualities they ascribed to Yahweh in comparison with or distinction from others elohim. If we understand that broader usage of the word 'god' in the ancient Jewish culture, this can help us understand the meaning of the aforementioned passages in Deuteronomy.
Michael Heiser argues that within an ancient understanding, both Yahweh and the divine figures we call 'angels' are 'gods' according to the ancient understanding of the word. However, it was an ontological quality that distinguished Yahweh as the unique, supreme God, which is what qualifies him alone for worship; all other gods (whether called 'gods', 'sons of God', or 'angels / messengers') are his creations, and thus unworthy of worship.3
While 'there are indeed many gods', the various biblical authors believed Yahweh was utterly unique and sovereign, with all other gods, real or not, inherently inferior.4
1 Cassius Dio, Roman History 67.14.2.
2 Compare the expressions: holy of holies (i.e. most holy), song of songs (greatest song), king of kings (supreme king), etc.
3 Heiser, 'The Divine Council in Late Canonical and Non-Canonical Second Temple Jewish Literature'.
4 This, for example, is why Paul, as a Jew from the Second Temple period, could say 'there are indeed many gods', but immediately turn around and say 'but for us there is one God, the Father, from whom are all things and for whom we exist'. (1 Corinthians 8.5-6).