I've heard it said that the Basque are conjectured to be the last remnant of Pre-Celtic Western Europe. When would have these people existed? What evidence do we have for their culture and habitation sites? When did they cede to the Celts?
Pre-Celtic inhabitants of western Europe included Bronze Age settlers, such as the Lusitaninans, Basques, Etruscans, and Belgae. As a commenter made clear, the Belgae inhabited modern Belgium and gave the area its current name.
Prior to that, we are talking about pre-historic cultures such as those that settled river valleys like the Dordogne in France.
By and large, we really don't know. The timing of archeological finds with the language distribution when the historical record opens makes a very compelling case for the Celto-Italics being the chief people who introduced farming to Western Europe. So any pre-Celtic inhabitants would have been Mesolithic (hunter-gatherers).
Neolithic (farming) societies support an order of magnitude larger population than hunter-gatherers, so from the Celts' perspective the Western European territory they were moving into would have barely been inhabited at all.
There were however some areas around the Mediterranean that managed to hit the Neolithic before the Indo-Europeans arrived. These are (probably not coincidentally) the areas that still had non- Indo-European societies when the historical record opens. The two main groups here are the Basques (who are still around) and the Tyrrhenians (who are not).
There are lots of theories about a possible prehistoric wider distribution for the Basque ancestors. Sadly most of these theories have been discredited. One that has not (but is still not really a majority opinion), is Vasconic, which is a name for a putative Basque ancestor covering all of Spain and the British Isles, and the western half of France.
Note that there are a couple more historical Iberean languages that may (or may not) have been non-IndoEuropean. More study needs to be done of these, but still I'd consider the Spanish portion of that map to be on a fair bit firmer foundation than the rest.
Tyrrhenian is a proposed common ancestor for the historical (now extinct) languages of Etruscan, Raetic, and Lemnan. This one is pretty well accepted.
"By and large, we really don't know. The timing of archeological finds with the language distribution when the historical record opens makes a very compelling case for the Celto-Italics being the chief people who introduced farming to Western Europe. So any pre-Celtic inhabitants would have been Mesolithic (hunter-gatherers)."
No. Farming arrived in parts of Western Europe by 5000 BC and was very widespread by 4000 BC. Proto-Celtic speakers left the steppes 3500 BC or later, as part of Gimbutas Wave 2 (e.g. Globular Amphora, Corded Ware/Battle Axe/Single Grave). When Western Europe switched to Celtic is unknown, but was surely later than 3000 BC, possibly much later. (Cite: Gimbutas-Mallory model.)
BTW, proto-Basque, rather than being a language of mesolithic Europe, probably arrived with some of the farmers. This is strongly claimed by some linguists (Cite "Another Member of Vasco-Caucasian?") due to apparent genetic connections among Basque, Burushaski, and some Caucasian languages, with a probable Neolithic time depth. (A word for 'goat' /zikiro/ is one of several example cognates, obeying regular sound change rules.)
There are many different, what might be called, "pre-Caucasian" ethnic communities in Europe that have been identified by archaeology. This terminology refers to the 19th-century idea that peoples originating in the Caucasus Mountains invaded and overcame various ancient races of Europe and central Asia. In 20th-century retrospect it seems reasonable to assume that it was not just Caucasian tribes that did this, but also Nordic and possibly Alpine tribes as well, so "Caucasian" may be too restrictive a term. This, by the way is the origin of the term "Caucasian" to describe Europeans in general.
From an anthropological point of view, Caucasian skeletons (and Nordic/Alpine) are distinctive because they large shoulders bones (the scapula and clavicle). When burial sites were dug up in the 19th century containing very ancient bones it was found the people had by contrast smaller, shorter shoulder bones, what a tailor today would call a "soft-shouldered" person. From this distinction was made between "modern" and "ancient" burials in Europe.
First of all, there is no such thing as "Celts" (Keltoi); that is a Greek word, simply meaning anyone to the north of Greece and basically means nothing. Usually when that word is used it refers to the Gaelic peoples. By their own tradition the Gaels were a Caucasian people who invaded first North Africa, then Spain, then Ireland and Britain, and finally Western Europe including what is now France, Holland, Denmark, and parts of Germany and Switzerland and Northern Italy. The people living in those areas prior to the invasion of the Gaels included many different aboriginal and non-aboriginal people.
Describing all the different known aboriginal peoples of Europe would take far too long, but I can summarize a few of them:
Basques (in northern Spain) [as you have already pointed out]
Maltese and Sicily ancient culture
Bell Beaker people (qv)
Scots (the people the Gaels called the "Ulaid" in northern Ireland)
Picts (the people the Gaels called the "Cruimthne" in Scotland)
Cumry (the Welsh)
Belgians (an ancient tribe existing in Holland and Belgium)
The Eagle Tomb people (northern Scotland)
The Iron Gate people (sites in Romania)
There are many others. It is notable that these people have not died out and their descendants live today, such as the Basques as just one example. These people often have primitive characteristics, such as having fingers of all equal length and having six fingers, for example.
In general, it is hard to explain why one culture defeats another, but from my own observations it tends to be a combination of superior physique, cultural freshness and flexibility, superiority of culture, access to the right natural resources at the right time, and development of superior technology.
If you are interested in ancient peoples, the "American Journal of Physical Anthropology" is a good source, and also the Peabody Museum of Harvard for many years published a journal called "Papers of the Peabody Museum of Archaeology and Ethnology" which is very informative and has much information on aboriginal cultures and anthropology.
There is a possibility that the pre Celtic inhabitants of Ireland at least, came from the Azov area of Ukraine, via Anatolia, Balkans, Sicily and Spain. The Old Irish Annals, which are oral histories written down in the medieval time, tell us that this is what happens. The latest archaeological data from the Balkans seems to be confirming that the Irish Annals could be actual remains of the real histories, describing events which happened 5000 years ago.
What the archaeological data is showing is that the first metalworkers who arrived in Ireland during the 3rd millennium bc could have come from Montenegro area of the Balkans. The culture which developed there during the early 3rd millennium BC has all the characteristics we later find in early metallurgical cultures of the British isles, particularly Ireland.
This early metallurgical culture in Montenegro descends directly from Yamna culture, but it has a distinct "flavor" only found in the Balkans and in Ireland and Britain at that time. What this means is that the expansion of this sub type of Yamna culture did not go through steppe, but along rivers and sea coast of the Black sea, Mediterranean and Atlantic. Basically they skipped the whole of continental Europe and settled the coastal areas and the river valleys. This is the culture which gave birth to Beakers of Western Europe and Ultimately to Celtic Europe. And if we look at the distribution of Beaker people in Europe we see that they are found in the coastal areas and the river valleys…
There is a strong possibility that linguistically these people spoke some kind of mixture of Celtic and Slavic languages, or more precisely the ancestral language of Gaelic and South Slavic languages, a sub dialect of the common Indoeuropean tongue. So it is quite possible that Gaelic was already spoken in Ireland in the 3rd millennium BC.
The latest genetic data actually confirms direct link between Beaker people of Ireland and the Yamna people from the Azov coastal area.
Aside: I've added OP's links and wikified, but I cannot emplace them in the text above (not within the time I have)