It's hard to say what the situation would have been as far back as 4500 BCE, because that's well before the invention of writing. The best evidence we have for how language worked back then comes from comparative reconstruction (comparing descendant languages against each other and figuring out what they could have evolved from), and this technique has serious limitations—that's the whole reason why the Proto-Indo-European Urheimat is still in question!
But we know that several indigenous non-Indo-European languages were spoken in Anatolia in the early 2000s BCE, because once writing was invented, they were recorded. We can find distinctly Hurrian-looking place names in Akkadian texts, for example, or words and phrases identified as "Hattic" in Hittite rituals. Later on, some of these languages (like Hattic) died out, but others (like Hurrian) were recorded more thoroughly, to the point that we have ancient bilingual (or trilingual or quadrilingual) dictionaries to help scribes learn them.
These languages are generally considered indigenous to Anatolia, because we don't know of anything that came before them, but it's entirely possible the Hurrian-speaking and Hattic-speaking peoples arrived somewhere around 3000 BCE, displacing earlier peoples who spoke completely different languages. There's just no way to be sure.
The only thing we can say for certain is that there were definitely non-Indo-European languages spoken in Anatolia around the beginning of recorded history, and most of them aren't known to be related to any larger language family. Given the linguistic diversity of the Bronze Age, I'd say it's a statistical certainty that there have always been non-Indo-European languages spoken in the area, but there's no evidence of what they might have been before the third millennium BCE.
