Is there evidence to support Deuteronomy being written before King Josiah?
Our Lord Jesus says
Our Lord Jesus believed Deuteronomy was not a "pious fraud" written in 621 BC but rather was written by Moses. (c.f. Matthew 19:7-8 with Deuteronomy 24:1-4):
Jesus replied, “Moses permitted you to divorce your wives because your hearts were hard. But it was not this way from the beginning.." (Matthew 19:8).
The only options then are either to believe that Deuteronomy was genuinely written by Moses in ancient times or to believe that the gospels are also pious frauds.
Excellent books to read are "A Survey of Old Testament Introduction" by Gleason Archer, 1964, which has several chapters (pages 73-166) on the Wellhausen Documentary Hypothesis, and its problems; and "Dating the Old Testament" by Craig Davis, 2007, with chapter 3 called "Dating the Torah" (pages 29 to 172). Both are conservative evangelicals and date Deuteronomy and the Pentateuch to the wilderness years sometime during the 15th to 13th century BC. (In fact, multiple lines of evidence prove the wilderness years were from 1446 to 1406 BC.) There is far too much evidence for the early authorship of the Torah/Pentateuch to discuss here.
Conservative evangelical evidence of early authorship of Pentateuch from Ezekiel 40:1 and the Seder Olam Rabbah
It's an extremely great pity that the articles of Rodger C. Young on the implications of the comments in the Seder Olam Rabbah on Ezekiel 40:1 are not common knowledge amongst Christians. If they were aware of these writings then every Christian would be aware that the Wellhausen Documentary Hypothesis is untenable. You can read his articles at Rodger Young's Papers on Chronology and the article of special relevance to the question is "The Talmud's Two Jubilees and Their Relevance to the Date of the Exodus", 2006. The two Jubilees are also relevant to the date of authorship of the Pentateuch as the articles will show. Rodger Young introduces this article thus:
This expands on the idea presented in the Solomon paper regarding the Jubilees. It shows that the remembrance of the Jubilees in the Talmuds, the Seder Olam, and in the Hebrew text of Ezek 40:1 allows a complete calendar of pre-exilic Sabbatical and Jubilee years to be constructed. This calendar shows that Israel's entry into Canaan, when counting started for these cycles, must have occurred in Nisan of 1406 BC, with the Exodus therefore in 1446 BC. This calculation of the date of the Exodus is independent of the method of calculating the date based on 1 Kgs 6:1, although both give the same date. Therefore counting must really have started at that time. The conclusion is drawn that the Book of Leviticus was in existence in 1406 BC, since no reasonable alternate source for the laws of the Jubilee and Sabbatical cycles has ever been postulated, and nations of the ancient Near East are known to have put ritual and cultic matters like this in writing.
The Samaritans have their own Torah(!)
It was not just the Jews who recognised the early Mosaic authorship of the Pentateuch but it was the enemies of the Jews also. The northern tribes separated from the southern in 931 BC at the death of Solomon. The northern tribes were then finally conquered by the Assyrians in 722 BC with yet more thousands of Israelites being exiled to other parts of the Empire (the process had already started before 722) and thousands being brought into the region of the northern tribes from other parts of the Empire. There thus started a religious syncretism in Samaria which was rejected by the Jews of Jerusalem. The Samaritans had (and have) their own Pentateuch (including Deuteronomy, of course) which is (almost) an exact copy of the Jewish Pentateuch. It is easy to understand why they would recognise the Pentateuch as authoritative if it was written before 931 BC, but why would they recognise it if it was a pious fraud written by the Jews, after the division of the kingdom into the northern tribes and Judaea in 931 BC? Would they not have scorned all pious frauds of their arch-enemies the Jews?
Written before the books of Ruth and Joshua, the knock-on effect of late authorship
Deuteronomy was written before the book of Ruth. The laws relating to a Kinsman-Redeemer spoken of in Ruth chapter 3 and implemented in chapter 4 are found in Deuteronomy 25:5-10.
The circumstances of Deuteronomy and the period and aims of King Josiah are very different. Josiah sought to encourage worship only at the Temple in Jerusalem and not at the "High Places". But Deuteronomy required worship on the mountains! (Deuteronomy 27:4-10) The book of Deuteronomy then runs counter to Josiah's aims.
This worship on the mountains was obeyed in the days of Joshua, including the proclamation of blessings and curses as required in Deuteronomy 27:11-26 (Joshua 8:30-35).
If Deuteronomy was written in 621 BC then it has a knock-on effect on the date of authorship of several other books of the Old Testament.
The city of Jerusalem is not once mentioned in the books of Moses
The following I paraphrase from Craig Davis book "Dating the Old Testament", 2007.
Jerusalem is named no less than 667 times in the Old Testament with the first mention in Joshua 10:1. But it is not mentioned once by name in the Torah. Several other locations in the land of Israel are mentioned including Shechem, Bethel, Bethlehem, Hebron and Beersheba, the last three all in the territory of Judah, like Jerusalem. This is explained by the fact that when the Torah was written Jerusalem could not have been an important city. But by the time of Josiah's reign Jerusalem had been the capital city for about 400 years!
The issue is sharpest with regard to Deuteronomy, a book the source critics allege was written with the express purpose of concentrating all worship in Jerusalem. Yet even though Deuteronomy mentions the high places of Mount Ebal and Mount Gerizim [which, by Josiah's time was a place for Samaritan worship] there is not a single mention of "Jerusalem". Likewise "Zion" which is often used as a substitute for Jerusalem and used 154 times in the Old Testament, is not found once in the Torah. (Craig Davis.)
Simply put, Deuteronomy could not have been written in the days of Josiah, about 600 bc, or even any time after 1000 bc by which time Jerusalem was the capital city.
Minor updates, including the city of "Rameses"
The Exodus from Egypt happened in 1446 BC and the Fall of Jericho and its walls happened in 1406 BC. Deuteronomy along with the rest of the Pentateuch was written in the wilderness between these two dates. There were very minor updates to the text for the next two or three hundred years by God-approved prophets. For instance, 1. the death of Moses is recounted which Moses obviously did not write. 2. The city of "Dan" is named in Genesis 14:14 in the days of Abraham, but it was not called Dan until it was conquered by the tribe of Dan (Judges 18:29). Clearly the name was updated at some point after the conquest by Dan to make more sense to the reader. 4. And "Ur of the Chaldees" (Genesis 11:28, 11:31, 15:7) is also likely a very late update to the original text. 5. The city of "Raamses" (Ex 1:11) which is "Rameses" (Gen 47:11, Ex 12:37, Numb 33:3,5) is mentioned. (The name is exclusive to the Pentateuch/Torah.) But it was not called Rameses in the days of Moses (it might have been called "Peru-nefer"). It only received that name (Pi-Ramesse - House of Rameses, see also Qantir; very close is Tell El'Daba (identified as Avaris, the Hyksos capital), in the 19th Dynasty during the reign of Rameses II (the Great) sometime between 1300 and 1220 BC. The city remained the capital until that distributary/branch of the Nile, the Pelusaic, silted up about 1030 BC and the capital moved to Tanis (- which is believed to be the Biblical "Zoan"). After that time the location and perhaps the memory altogether of Rameses was forgotten until modern archaeology rediscovered the site.
The point is that naming a town "Rameses" would have been almost entirely meaningless to the Jewish readers in the days of Josiah, 640 to 609 BC: no city by that name had existed for at least four hundred years. It is questionable whether the Israelites or even most Egyptians at that time had ever heard of the city of Rameses. An update of the city name to "Rameses" in the Pentateuch would have most likely happened during the years 1300 to 1030 BC when the modern site of Qantir was the heart of the huge city of that name.
Deuteronomy, on this evidence alone, was not written in the days of Josiah.