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.
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.)