What you are actually asking (but might not realize) is when was regeneration first associated with the moment of 'first' having faith, rather than at the time of baptism. 'Born again' and 'regeneration' have always been synonymous or at least the initial point of regeneration.
So unfortunately we have to trace attitudes of baptism with respect to regeneration for adults. Aside from entering into the doctrine as the Bible introduces it, for from that angle many will say the ideas was first introduced there, I am just going to trace the history. So let's keep the Apostolic age unknown as some believe the early church fathers immediately fell into superstition on the subject and did not maintain the Apostolic practice, while others think they did maintain it.
Regarding the church fathers, they generally associated regeneration with a magical sort of baptism. What I mean is that the baptism actually produced the regeneration state, so that one was justified, born again, forgiven, became a member of the body of Christ, died to sin, etc., at the moment of baptism.
Probably the first focus on faith rather than baptism is with Luther and then also various leaders of the reformation. Luther kept conservative about baptism and so for an adult one can see regeneration happening by faith but not really being a true regeneration or a completed one without the baptism. However, Luther sort of saw himself as unregenerate until having come to faith, but that faith combined with his baptism as a child, made the regeneration true and complete. Luther is kind of confusing on this matter because he was very intent on keeping any church tradition that was not directly opposed by clear scripture. As he wanted a theology to maintain infant baptism, in response to the anabaptists that wanted to re-baptize people after they first believed, Luther became more conservative than he originally seemed to be on the subject.
However in Luther's own experience when it became clear to him that a man is justified and born again by faith only, apart from works, he actually describes this event as being born again himself:
Luther’s Own Testimony (1545)
The most important statement of the mature Luther concerning his breakthrough is his so-called self-witness. It appears in the preface to the first volume of Luther’s collected works. The most significant portions read:
Meanwhile, I had already during that year returned to interpret the Psalter anew. I had confidence in the fact that I was more skilful, after I had lectured in the university on St. Paul’s epistles to the Romans, to the Galatians, and the one to the Hebrews. I had indeed been captivated with an extraordinary ardor for understanding Paul in the Epistle to the Romans. But up till then it was not the cold blood about the heart, but a single word in Chapter 1 [:17], “In it the righteousness of God is revealed,” that had stood in my way. For I hated that word “righteousness of God,” which, according to the use and custom of all the teachers, I had been taught to understand philosophically regarding the formal or active righteousness, as they called it, with which God is righteous and punishes the unrighteous sinner. Though I lived as a monk without reproach, I felt that I was a sinner before God with an extremely disturbed conscience. I could not believe that he was placated by my satisfaction. I did not love, yes, I hated the righteous God who punishes sinners, and secretly, if not blasphemously, certainly murmuring greatly, I was angry with God, and said, “As if, indeed, it is not enough, that miserable sinners, eternally lost through original sin, are crushed by every kind of calamity by the law of the decalogue, without having God and pain to pain by the gospel and also by the gospel threatening us with his righteousness and wrath!” Thus I raged with a fierce and troubled conscience. Nevertheless, I beat importunately upon Paul at that place, most ardently desiring to know what St. Paul wanted.
At last, by the mercy of God, meditating day and night, I gave heed to the context of the words, namely, “In it the righteousness of God is revealed, as it is written, ‘He who through faith is righteous shall live.’ ” There I began to understand that the righteousness of God is that by which the righteous lives by a gift of God, namely by faith. And this is the meaning: The righteousness of God is revealed by the gospel, namely, the passive righteousness with which the merciful God justifies us by faith, as it is written, “He who through faith is righteous shall live.” Here I felt that I was altogether born again and had entered paradise itself through open gates. There a totally other face of the entire Scripture showed itself to me. Thereupon I ran through the Scriptures from memory. I also found in other terms an analogy, as, the work of God, that is, what God does in us, the power of God, with which he makes us strong, the wisdom of God, with which he makes us wise, the strength of God, the salvation of God, the glory of God.
And I extolled my sweetest word with a love as great as the hatred with which I had before hated the word “righteousness of God.” Thus that place in Paul was for me truly the gate to paradise. Later I read Augustine’s The Spirit and the Letter, where contrary to hope I found that he, too, interpreted God’s righteousness in a similar way, as the righteousness with which God clothes us when he justifies us. Although this was heretofore said imperfectly and he did not explain all things concerning imputation clearly, it nevertheless was pleasing that God’s righteousness with which we are justified was taught. (MARTIN LUTHER’S THEOLOGY, Its Historical and Systematic Development, BERNHARD LOHSE, p91 )
Of course the Baptists at this time definitely held the view that regeneration / new birth occurred without the need for baptism and that baptism was just symbolic to show the past event. So in some sense you already have the answer. The usage of born again to first believing as already popular by many in the 1500s.
However to keep tracing the slow emerging separation of regeneration and baptism among the reformed leaders who opposed the re-baptism or infant baptism let's look at Calvin. Calvin though still putting a lot of emphasis on baptism, started focusing on regeneration clearly before baptism.
Calvin clearly associates 'born again' to initial conversion through repentance which is also the same as regeneration in his mind:
Repentance is preached in the name of Christ, when men learn, through the doctrines of the Gospel, that all their thoughts, affections, and pursuits, are corrupt and vicious; and that, therefore, if they would enter the kingdom of God they must be born again. Forgiveness of sins is preached when men are taught that Christ “is made unto us wisdom, and righteousness, and sanctification, and redemption,” (1 Cor. 1:30,) that on his account they are freely deemed righteous and innocent in the sight of God. (Calvin's Institutes 2.173)
To Calvin, regeneration and being born again is really the immediate result of an irresistible call of God according to God's predestined plan justifying the sinner by faith and causing them to enter into a new life in the Spirit as a immediate subsequently result of being a justified sinner:
The special election which otherwise would remain hidden in God, he at length manifests by his calling. “For whom he did foreknow, he also did predestinate to be conformed to the image of his Son.” Moreover, “whom he did predestinate, them he also called; and whom he called, them he also justified,” that he may one day glorify, (Rom. 8:29, 30.) Though the Lord, by electing his people, adopted them as his sons, we, however, see that they do not come into possession of this great good until they are called; but when called, the enjoyment of their election is in some measure communicated to them. For which reason the Spirit which they receive is termed by Paul both the “Spirit of adoption,” and the “seal” and “earnest” of the future inheritance; because by his testimony he confirms and seals the certainty of future adoption on their hearts. (Calvin's Institutes 2.580)
The next stop, of a conservative reformed theologian, is John Owen around 100 years after Calvin. As with most things Owen is very clear, leaving little room to misunderstand his refined distinctions:
Thirdly, Our conversion is a “new creation,” a “resurrection,” a “new birth.” Now, he that createth a man doth not persuade him to create himself, neither can he if he should, nor hath he any power to resist him that will create him,—that is, as we now take it, translate him from something that he is to what he is not. What arguments do you think were sufficient to persuade a dead man to rise? or what great aid can he contribute to his own resurrection? Neither doth a man beget himself; a new real form was never yet introduced into any matter by subtle arguments. These are the terms the Scripture is pleased to use concerning our conversion:—“If any man be in Christ, he is a new creature,” 2 Cor. 5:17. The “new man after God is created in righteousness and true holiness,” Eph. 4:24. It is our new birth: “Except a man be born again, he cannot see the kingdom of God,” John 3:3. “Of his own will begat he us with the word of truth,” James 1:18. And so we become “born again, not of corruptible seed, but of incorruptible, by the word of God, which liveth and abideth for ever,” 1 Pet. 1:23. It is our vivification and resurrection: “The Son quickeneth whom he will,” John 5:21, even those “dead,” who “hear his voice and live,” verse 25. “When we were dead in sins,” we are “quickened together with Christ by grace,” Eph. 2:5; for “being buried with him by baptism, we are also risen with him through the faith of the operation of God,” Col. 2:12. And “blessed and holy is he that hath part in that first resurrection; on such the second death hath no power, but they shall be priests of God and of Christ, and shall reign with him a thousand years. (John Owen's Works 10.136)
I have not mentioned that the Baptists who were originally more Arminian but have largely become reformed Calvinists, have become mainstream since the reformation and probably have partly influenced the average evangelical to have even more clear distinction of original faith, regeneration and the born-again state, as opposed to mere outward baptism. The methodists also would have had an influence on the same. In the end, for over a hundred years, outside of Catholic or very traditional branches of Lutheran and Anglican, the born again experience is synonymous with regeneration and happens before baptism in water. The focus started in the reformation in the 1500s.
Although regeneration is imagined a momentary event by faith, apart from works, a personal assurance of the event or clear identification of when it happened is a different subject. Many people are not sure when it really happened. Also most churches feel that one must prove to themselves that they have the Spirit by a renovated life before assuming that they have ever yet been born again.