[My apologies to those who get this twice.  I am crossposting this
to both CONLANG and lostlangs.]

What can we say about the languages of Europe prior to the spread
of Indo-European?  Unfortunately, not very much; we are indeed
dealing with a lost world here.

However, this world is not lost without traces.  Indeed, some
of those pre-Indo-European languages have survived: Basque in
the western Pyrenees, and three families with together about
three dozen - fascinating - languages in the Caucasus (see
http://www.joerg-rhiemeier.de/Conlang/caucasian.html for some
information about those languages).  Also, we have some written
documents in extinct non-Indo-European languages once spoken
in southern Europe, such as Etruscan, Iberian (apparently
*not* related to Basque) and Eteocretan; however, only Etruscan
has been deciphered to some degree so far - the others are too
fragmentarily attested.  (The Uralic languages in the north and
east of Europe are probably no pre-Indo-European survivors; the
Uralic family is about the same age as the Indo-European one,
and spread in tandem with the latter.)

Certainly, these languages have changed since the time when
Indo-European and Uralic displaced most of the other languages
spoken before their expansion, but if we assume that they are
more or less representative examples of pre-Indo-European
languages, we can say a bit about the typology of the pre-IE
European languages.  Basque and the Caucasian languages are
highly synthetic bordering on the polysynthetic, so it is
reasonable to assume that high degrees of morphological
synthesis were characteristic of pre-IE Europe.  Etruscan
is a bit less synthetic, comparable in this regard with Latin
or Greek (which still is a quite high degree of synthesis).
Basque and most Caucasian languages, but not Etruscan, are
ergative, so there probably were many ergative languages in
pre-IE Europe.

How many languages and families were there?  A good comparison
for Neolithic Europe probably is pre-colonial North America.
In the area that is now the United States and Canada, there
were at least 300 languages falling into about 50 families.
Europe is about half the size of that area, so we get something
like 150 languages in 25 families.  Of course, there is a large
margin of error in this estimation.

An important question is: when did Indo-European spread?  There
are, aside from crackpot notions such that the Indo-European
languages came from Atlantis or other unlikely locations, two
hypotheses seriously discussed:

1. Proto-Indo-European was spoken about 6,000 years ago in the
   area north of the Black Sea, and Indo-European spread in the
   Copper Age from there in a wave of more or less military
   conquests.  This is the "Kurgan hypothesis".

2. Proto-Indo-European was spoken about 9,000 years ago in
   Anatolia, and spread together with Neolithic farming.
   This is the "Anatolian hypothesis".

The Anatolian hypothesis is very fashionable today, as it
portrays our (linguistic) ancestors as peaceful farmers rather
than aggressive conquerors, but what counts here is not what
is fashionable, but what explains the facts.  And the facts
speak strongly for the Kurgan hypothesis, even if the popular
notion that the Proto-Indo-Europeans were nomads must be
abandoned.  Proto-Indo-European, as we can reconstruct it,
had words for wheeled vehicles and their parts, as well as
for the metals copper, silver and gold, and domestic horses.
All these set an earliest possible date at about 4000 BC.
It is a telltale sign that the Anatolian hypothesis is most
popular among non-linguists who are not aware of the facts
mentioned above, while the linguists overwhelmingly prefer
the Kurgan hypothesis.

Also, it is questionable whether the Neolithic farmers of
central Europe (such as the Linear Pottery culture) came
from Anatolia.  There do not appear to be particular
cultural similarities.  Recently, geologists found evidence
for a catastrophic flooding of the Black Sea basin, which,
according to the theory, held a freshwater lake with a
level about 100 metres lower than the present sea level
until the ocean burst through the Bosporus about 8,000
years ago (the exact date is still controversial, the
proposals ranging from 6,700 BC to 5,500 BC).  Before that
disaster, there must have been fertile plains where now
are the Bay of Odessa and the Sea of Azov.  These plains
were probably inhabited by a flourishing Neolithic culture.
When the Bosporus dam burst, these people fled up the
great rivers flowing into the Black Sea to escape the
deluge.  (They probably travelled by boat, with the horse
not yet domesticated and the wheel not yet invented.)
Some moved north on the Dniepr and became the ancestors
of the Indo-Europeans; others moved west on the Danube
and settled central Europe.  They probably spoke languages
related to Indo-European.

Is there linguistic evidence for a sister group of Indo-
European in central Europe?  There seems to be, although
it is not all too clear.  In the middle of the 20th
century, the German linguist Hans Krahe identified a
linguistically rather uniform network of river names,
which he called the "Old European hydronymy", spanning
most of central Europe, southern Scandinavia, France,
the British Isles and parts of Italy and the Iberian
peninsula.  He considered these river names to be Indo-
European, but there are problems with that: while many
of the names appear to make sense in Indo-European, they
do not exhibit the sound correspondences expected if
inherited from Proto-Indo-European.  It is especially
the vowels that are odd, with /a/ all over the place
where one would expect /e/ or /o/ if the names were
Indo-European.  Another German linguist, Theo Vennemann,
assumed that the names were not Indo-European at all,
but "Vasconic", i.e. from languages related to Basque.
However, he could only make them fit by applying brute
force and intermediate substrata such as an Italic
substratum in Germany and Britain(!) to explain the
spirants which occur in the names in that area.

In my opinion, the best explanation for the "Old European
hydronymy" is a family of languages related to Indo-
European, but splitting off about 2,000 years earlier
(namely, when the Black Sea Flood struck), at a time
when the Indo-European ablaut had not happened yet and
the language had a three-vowel system */a i u/ (of which
/a/ was markedly more common than the others).  I use
the term "Hesperic" for this hypothetic language family,
while I propose the term "Europic" for the larger unit
that includes Indo-European and Hesperic.  Yet, Hesperic
evidently did not displace earlier languages to the same
degree as Indo-European did - the fact remains that no
Hesperic language survived, while some languages from
earlier layers of settlement did.

Another way of gaining knowledge about lost European
languages is searching for substratum influences in the
Indo-European languages of Europe.  Such influences are
usually most manifest in phonology and syntax.  Regarding
syntax, many European language form a kind of language
area known as "Standard Average European" (see
http://www.joerg-rhiemeier.de/Conlang/sae.html ); this
area, however, probably does not hark back to Neolithic
times, but is the result of ongoing language contact
since the Völkerwanderung until today - that is is an
ongoing process can be seen in western Slavic languages
such as Czech and Slovenian, whose colloquial verieties
are more "SAE" than the literary standards.

Basque and the Caucasian languages are outside the SAE
area.  Most of these languages show an SOV word order,
which is also reconstructed for PIE.  A group of languages
for whose "weirdness" a substratum is often held resposible
are the Insular Celtic languages with their VSO word order
and initial mutations.  Some scholars (including the
aforementioned Vennemann) assume a Semitic substratum here,
but there is actually no valid reason to assume that.
Most likely is a Hesperic language that had developed a
verb-initial order, possibly from contact with a pre-
Neolithic language group.

Regarding morphosyntactic alignment, Europe is now dominated
by accusative languages, but that is the result of the
spread of Indo-European and Uralic.  Basque is ergative,
and so are most Caucasian languages.  Proto-Indo-European
of course was accusative, but seems to have evolved from an
active/stative language, which Hesperic may still have been.

Now, phonology.  I already have mentioned that Hesperic seems
to have had a three-vowel system inherited from Proto-Europic.
The consonant inventories of modern European languages seem
to follow an east-west cline, with more copious inventories,
especially regarding sibilants and affricates, in the east.
The Caucasian languages are famous for their rich consonant
inventories.  It may well be that this east-west cline already
existed in the prehistoric linguistic landscape.

In short, there are some tantalizing hints at what the
lingusitic landscape of Europe may have looked like before
the spread of Indo-European, but much remains unknown.
Most likely, however, Europe was much more colourful and
fascinating, what regards languages, than it is today.
A great playground for conlangers!

... brought to you by the Weeping Elf