Crucifixion seems to be always and everywhere associated with the Roman Empire, the dissident slaves along the Appian Way, that dude from Nazareth, etc. But I have just read that Polycrates the tyrant of Samos was put to death by crucifixion in the sixth century BCE when Rome was still a kingdom – so how far back can we trace crucifixion, what is the earliest documented instance that we know of?
Keep in mind that 'crucifixion' means a variety of things to do with suspension and torture, and it's only after the crucifixion of Jesus does it come to mean what happened to him (nails etc.,).
Homer is the earliest person who talks about crucifixion (in the former sense), with Odysseus and Eumaios (22nd book of the Odyssey), where Odysseus talks about hanging Melanthius up from the roof beams to cause him pain, and that's probably the first written account. The other Archaic era crucifixion is probably Aesop with a reference in the murderer and the mulberry tree. The English is more specific than the Greek.
Those are our earliest references to 'crucifixion'.
Polycrates' death is a bit vague (like Homer's account) because it could either be impalement or crucifixion (suspension), and it doesn't describe an execution but a post-mortem suspension (cf Gunnar's Crucifixion in Antiquity).