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 YHWH, 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', even though 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 YHWH. For example, in Exodus 12:12 YHWH claims he will 'execute judgment on all the gods of Egypt'. Psalm 82 portrays God as sitting in judgment amidst a heavenly council of gods. YHWH is called 'the god of gods' on more than one occasion, an idiom that means 'the greatest god'.2
What this shows is that the common modern definition of the word 'god' (an omnipotent, omniscient supernatural entity) does not correspond very well to the ancient near eastern concept of '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 or not, but what qualities they ascribed to YHWH that distinguished him from those other 'gods' as they used the term. 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 YHWH and the angels are 'gods', but the qualitative difference was that YHWH is the sole, almighty uncreated god, which is what qualifies him alone for worship, while all other gods (also called 'sons of God' or 'angels', the latter just designating their roles as YHWH's messengers) are his creations, and thus unworthy of worship.3
So while 'there are indeed many gods', the various biblical authors believed YHWH was utterly supreme and unique, and all other gods (whether they existed or not) were 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).