So its recorded that the celts arrived in Britain around 500BC, then what was the pictish language before this?
Nobody actually recorded when Celtic-speaking peoples arrived in Britain. The Mediterranean world was entirely unaware of Britain until the 4th century BC (the journeys of Pytheas of Massilia), and the Romans didn't visit Britain until the 1st century BC (Caesar's expedition during the Gallic Wars).
From the archaeological perspective, the people known to the Greeks/Romans as Celts/Gauls were the bearers of the iron age culture of La-Tène. Iron working entered Britain around 800 BC (it entered Ireland even later), but the typical La-Tene style didn't arrive in Britain until ca. 500 BC. Does that mean that Celtic languages as a whole arrived only then? I find that highly doubtful, especially considering that Ireland was wholly Celtic by historic times yet from the archaeological only received a peripherial influence from the La-Tene culture.
It is thus my opinion that there probably were several waves of Celtic migrations towards the British Isles. The first wave during the great upheavals of the bronze age (13-12th century BC, coinciding roughly with the collapses of the civilizations in the eastern Mediterranean) bringing a Proto-Celtic (Q-Celtic) language to Britain, and a second wave during the iron age bringing a P-Celtic language to Britain.
From the genetic perspective, this may be reflected by Y-Haplogroups R1b-L21 and R1b-U152, but I'd be cautious with such an interpretation.
There are some people who propose that the Beaker-Bell Culture (3rd millennium BC) was already Celtic, but I have my serious doubts that it was even Indo-European at all, partially due to it's continuity with the earlier Megalithic traditions, partly due to it's age and due to it's very widespread nature (including North Africa and Sardinia).
Some historians say the picts where from western France related to the basques, some say they are related to the spanish Galicians and others say they where scandinavian people as they where great seafarers.
From my expirience, these are just urban legends. At least, I am unaware of a single reference in peer-reviewed sources of any of the above statements.
The Romans only mentioned them once physically
"Venit et extremis legio praetenta Britannis, Quae Scotto dat frena truci ferronque notatas Perlegit examines Picto moriente figuras"
- The Romans called this pre-Celtic people Pictii, or "Painted ones"
Caesar clearly stated that the British
as a whole painted themselves blue.
Bello Gallico, Book 5, chapter 14:
"Omnes vero se Britanni vitro inficiunt, quod caeruleum efficit colorem, atque hoc horridiores sunt in pugna aspectu."
"All the Britons, indeed, dye themselves with woad, which occasions a bluish color, and thereby have a more terrible appearance in fight."
- The Picts spoke a non-Celtic language, although many Celtophiles feel the Picts spoke a Brythonic-Gaulish form of Celtic language. As I stated, since celtic only arrived in britain from 500BC, the pre langauge of the islands was not celtic based.
The little evidence that there is of the Pictish language that there is in Graeco-Roman and (much later) Gaelic sources suggests that it was a P-Celtic language akin to ancient Brythonic and Gaulish.
It is my opinion that prior to the Roman invasion of Britain (1st century BC/AD), there probably was little difference between inhabitants of southern and northern Britain, and the difference between "Britons" and "Picts" was a product of the Hadrian's Wall. So, by the time the Romans withdrew from Britain (5th century AD), Brythonic and Pictish were two different languages.
Again I will ask the question, is celtic related to a language or a people. .........my answer is that it is a language.
In the context of linguistics, "Celtic" obviously refers to the Celtic language family.