When and where was it firstly stated in the history of Christianity that a human being has a personal freedom of choice and that God respects it?
The exact meaning of "free will" is greatly contested, especially as it interacts with the sovereign power and foreknowledge of God. I understand your question as seeking evidence for early Christian thought, other than in the content of the Bible itself.
In the early church, several authorities wrote on the topic, in support of human freedom, including the following.
Justin Martyr in his First Apology (written at some point between 147 and 161AD), says: "But lest some suppose, from what has been said by us, that we say that whatever happens, happens by a fatal necessity, because it is foretold as known beforehand, this too we explain. [...] Unless the human race have the power of avoiding evil and choosing good by free choice, they are not accountable for their actions, of whatever kind they be. [...] For not like other things, as trees and quadrupeds, which cannot act by choice, did God make man: for neither would he be worthy of reward or praise did he not of himself choose the good, but were created for this end; nor, if he were evil, would he be worthy of punishment, not being evil of himself, but being able to be nothing else than what he was made."
Irenaeus in Against Heresies 4.37 (c. 180 AD) says: "God made man a free [agent] from the beginning, possessing his own power, even as he does his own soul, to obey the behests of God voluntarily, and not by compulsion of God. For there is no coercion with God, but a good will [towards us] is present with Him continually. [...] All men are of the same nature, able both to hold fast and to do what is good; and, on the other hand, having also the power to cast it from them and not to do it. [...] It is in man's power to disobey God, and to forfeit what is good; but [such conduct] brings no small amount of injury and mischief. [...] And not merely in works, but also in faith, has God preserved the will of man free and under his own control."
Origen devotes the third book of De Principiis (c. 212 - 215 AD) to the free will doctrine. At the beginning of the Latin text is the firm statement, "It is undoubtedly indicated that it is within our own power to devote ourselves either to a life that is worthy of praise, or to one that is worthy of censure."
Aside from these philosophical treatments, there are writings of the post-apostolic generation which indicate of a role for human will in choosing to do good or evil.
The letter of Clement to the Corinthians (c. 70 - 96 AD?) exhorts readers to live a virtuous life; in 62.1 he characterizes the faithful as "those who are willing to make [the journey]" (τοις θελουσιν ... διευθυνειν [την πορειαν αυτων]), where the Greek θελουσιν comes from the verb ἐθέλω or θέλω, indicating wishing/wanting/desiring.
The Didache, or Teaching of the Twelve Apostles (date very contested, perhaps 50 - 120 AD) contrasts "the way of death" with "the way of life" and suggests that it is up to the individual not to be led astray from the true teaching. Didache 6.1-2 is translated by Robert Kraft as "Beware lest anyone cause you to wander from this way of teaching, since such a one teaches without regard to God. For if you can bear the whole yoke of the Lord, you will be perfect; but if you cannot, do what you can."
The letter of Barnabas (70 - 131 AD) says that the one who follows God's commands will be rewarded, but the one who chooses the opposite will be destroyed (21.1). The word for this chooser is "ἐκλεγόμενος", from "ἐκλέγω" (pick/select/choose). It may still refer to God's choice, though; compare Ephesians 1:4 where the same word is used for God's foreordained choice of the elect.
ACC: In the Garden of Eden, God gave freedom of choice to Adam and Eve. This was His greatest gift to them, since they had been created. Until Adam ate of the tree of good and bad, he had no idea that he was separate from God, or that he could do something on his own (without God telling him to do it.) This idea comes from Midrash (3rd. cent. C.E.,) and was discussed by the Fathers of the 4th. cent. (It will take some time to find the references. Probably Jerome, or perhaps Origen.)
In the 5th. cent. whether or not Jesus had a free will was a heated topic. In the Creeds of The Church they finally decided Jesus had two wills, one very human and one divine, so he was free to disobey God, but chose not to.