A cursory search of the Internet brought me this list of quotations from various patristic sources.
Righteous Job the Long-Suffering (1000 – 300 BC)
If there shall be an angel speaking for him . . . He shall have mercy
on him, and shall say: Deliver him, that he may not go down to
corruption" (Job xxxiii, 23).
Book of Tobit (~ 200 – 100 BC)
When thou didst pray with tears… I [Archangel Raphael] offered thy
prayer to the Lord. (Tobit xii, 12)
St. John the Evangelist (+101)
And another angel came, and stood before the altar, having a golden
censer; and there was given to him much incense, that he should offer
of the prayers of all saints upon the golden altar, which is before
the throne of God. And the smoke of the incense of the prayers of the
saints ascended up before God from the hand of the angel. (Apoc.,
viii, 3, 4)
St. Cyprian of Carthage (+258), writing to Pope Cornelius of Rome
Let us be mutually mindful of each other, let us ever pray for each
other, and if one of us shall, by the speediness of the Divine
vouchsafement, depart hence first, let our love continue in the
presence of the Lord, let not prayer for our brethren and sisters
cease in the presence of the mercy of the Father.[iv]
St. Hilary of Poitiers (+368)
To those who would fain stand, neither the guardianship of saints nor
the defences of angels are wanting.[v]
St. Ephraim the Syrian (+373)
Remember me, ye heirs of God, ye brethren of Christ, supplicate the
Saviour earnestly for me, that I may be freed though Christ from him
that fights against me day by day.[vi]
Ye victorious martyrs who endured torments gladly for the sake of the
God and Saviour; ye who have boldness of speech towards the Lord
Himself; ye saints, intercede for us who are timid and sinful men,
full of sloth, that the grace of Christ may come upon us, and
enlighten the hearts of all of us that so we may love him.[vii]
St. Athanasius the Great, Patriarch of Alexandria (+373)
Christ became man that men might become gods[viii]
“In one of his letters, St. Basil [the Great] explicitly writes that
he accepts the intercession of the apostles, prophets and martyrs, and
he seeks their prayers to God. (Letter 360) Then, speaking about the
Forty Martyrs, who suffered martyrdom for Christ, he emphasizes that
they are common friends of the human race, strong ambassadors and
collaborators in fervent prayers. (Chapter 8)
“St. Gregory of Nyssa asks St. Theodore the Martyr …to fervently pray
to our Common King, our God, for the country and the people (Encomium
to Martyr Theodore).
“The same language is used by St. Gregory the Theologian in his
encomium to St. Cyprian. St. John Chrysostom says that we should seek
the intercession and the fervent prayers of the saints, because they
have special "boldness" (parresia), before God. (Gen. 44: 2 and
Encomium to Julian, Iuventinus and Maximinus, 3).”[ix]
St. Basil the Great, of Caesarea in Asia Minor (+379)
According to the blameless faith of the Christians which we have
obtained from God, I confess and agree that I believe in one God the
Father Almighty; God the Father, God the Son, God the Holy Ghost; I
adore and worship one God, the Three. I confess to the economy of the
Son in the flesh, and that the holy Mary, who gave birth to Him
according to the flesh, was Mother of God. I acknowledge also the holy
apostles, prophets, and martyrs; and I invoke them to supplication to
God, that through them, that is, through their mediation, the merciful
God may be propitious to me, and that a ransom may be made and given
me for my sins. Wherefore also I honour and kiss the features of their
images, inasmuch as they have been handed down from the holy apostles,
and are not forbidden, but are in all our churches.[x]
We beseech you, O most holy martyrs, who cheerfully suffered torments
and death for his love, and are now more familiarly united to him,
that you intercede with God for us slothful and wretched sinners, that
he bestow on us the grace of Christ, by which we may be enlightened
and enabled to love him.[xi]
O holy choir! O sacred band! O unbroken host of warriors! O common
guardians of the human race! Ye gracious sharers of our cares! Ye
co-operators in our prayer! Most powerful intercessors![xii] Liturgy
of St. Basil the Great
By the command of Thine only-begotten Son we communicate with the
memory of Thy saints . . . by whose prayers and supplications have
mercy upon us all, and deliver us for the sake of Thy holy name which
is invoked upon us.[xiii]
St. Cyril of Jerusalem (+386)
We then commemorate also those who have fallen asleep before us,
first, patriarchs, prophets, apostles, martyrs, that God, by their
prayers and intercessions, may receive our petitions.[xiv]
St. Gregory the Theologian, Patriarch of Constantinople; of Nazianzus in Asia Minor (+389)
Mayest thou [Cyprian] look down from above propitiously upon us, and
guide our word and life; and shepherd [or shepherd with me] this
sacred flock . . . gladdening us with a more perfect and clear
illumination of the Holy Trinity, before Which thou standest.[xv]
St. Gregory of Nyssa in Lower Armenia (+395-400)
...I wish to commemorate one person who spoke of their noble testimony
because I am close to Ibora, the village and resting place of these
forty martyrs' remains. Here the Romans keep a register of soldiers,
one of whom was a guard ordered by his commander to protect against
invasions, a practice common to soldiers in such remote areas. This
man suffered from an injured foot which was later amputated. Being in
the martyrs' resting place, he earnestly beseeched God and the
intercession of the saints. One night there appeared a man of
venerable appearance in the company of others who said, "Oh soldier,
do you want to be healed [J.167] of your infirmity? Give me your foot
that I may touch it." When he awoke from the dream, his foot was
completely healed. Once he awoke from this vision, his foot was
restored to health. He roused the other sleeping men because he was
immediately cured and made whole. This men then began to proclaim the
miracle performed by the martyrs and acknowledged the kindness
bestowed by these fellow soldiers…. We who freely and boldly enter
paradise are strengthened by the [martyrs'] intercession through a
noble confession in our Lord Jesus Christ, to whom be glory forever
and ever. Amen.[xvii]
Do thou, [St. Ephraim the Syrian] that art standing at the Divine
altar, and art ministering with angels to the life-giving and most
Holy Trinity, bear us all in remembrance, petitioning for us the
remission of sins, and the fruition of an everlasting kingdom.[xviii]
St. Ambrose of Milan (+397)
May Peter, who wept so efficaciously for himself, weep for us and turn
towards us Christ's benignant countenance.[xix]
St. Jerome, b. Dalmatia, d. Palestine (+419)
If the Apostles and Martyrs, while still in the body, can pray for
others, at a time when they must still be anxious for themselves, how
much more after their crowns, victories, and triumphs are won! One
man, Moses, obtains from God pardon for six hundred thousand men in
arms; and Stephen, the imitator of the Lord, and the first martyr in
Christ, begs forgiveness for his persecutors; and shall their power be
less after having begun to be with Christ? The Apostle Paul declares
that two hundred three score and sixteen souls, sailing with him, were
freely given him; and, after he is dissolved and has begun to be with
Christ, shall he close his lips, and not be able to utter a word in
behalf of those who throughout the whole world believed at his
preaching of the Gospel? And shall the living dog Vigilantius be
better than that dead lion?[xx]
St. John Chrysostom, Patriarch of Constantinople; b. Antioch, Syria (+407)
When thou perceivest that God is chastening thee, fly not to His
enemies . . . but to His friends, the martyrs, the saints, and those
who were pleasing to Him, and who have great power [parresian,
"boldness of speech"].[xxi]
He that wears the purple, laying aside his pomp, stands begging of the
saints to be his patrons with God; and he that wears the diadem begs
the Tent-maker and the Fisherman as patrons, even though they be
dead.[xxii]
St. Augustine of Hippo, in North Africa (+430)
At the Lord's table we do not commemorate martyrs in the same way that
we do others who rest in peace so as to pray for them, but rather that
they may pray for us that we may follow in their footsteps.[xxiii]
One would expect the Masoretic Old Testament to have little support for prayer requests to the dead, as opposed to prayer requests for the dead, since (is this correct?) the notion of resurrection was a later introduction to Judaism in preparation for the coming of Christ. Indeed, the Psalmist declares
Indeed death held illimitable dominion over all, even the righteous, before the glorious victory of our Lord Jesus. But now even (or especially) Christian children spit upon death as upon a miscreant pilloried, or better, a great foe vanquished and made impotent. Death is now (among other things) an entrance into new life, life in Christ.
I suspect the main basis for this practice is that "it seemed good to the Holy Spirit and to us." After doing the work of God (viz. liturgy, specifically communing) at the tombs of the martyrs (or today, celebrating the liturgy upon the relics of saints), it is not farfetched to give death the finger by submitting prayer requests to these "dead," now made alive in Christ Jesus (presuming they've made it there). Indeed, the revelation of John tells us that departed saints continue to pray; it is then not farfetched to hope that they might hear our petitions and pray for what we ask. Indeed, now that they are truly baptized with the baptism with which He has been baptized, it's that much more easy to ask them to intercede for us than it is to ask those still in the flesh to pray for us. Petitioning the saints comes from knowledge in the Spirit that they will know what we ask, and pray for us accordingly.
Assuredly, however, a more detailed and specifically history/archaeology-based answer to your question would be more appropriate than such speculation. I hope the list above is helpful.
This all represents my understanding of the practice of veneration of and petitioning to the saints who have died, as an Eastern Orthodox Christian.