When did the LDS church start teaching that God the Father had a beginning?

The "assertion" that God was once a man despite the characterization here that it is uniquely "Mormon" doctrine, begs the obvious point that God was in fact a fully human man in the person of Jesus Christ. To use this doctrine to try an allege a fundamental difference between "Mormonism" and Christianity is either to deny Christ was human or, is based upon the notion of the relevance of the time and date that God experienced humanhood. The entire point of the doctrine is being missed here. It has more to do with the potential of mankind, than the history of God. In fact, the "Mormon couplet" " AS man now is, God once was; As god now is, man may be" (Lorenzo Snow, 5th president of the Mormon Church", is a minor expansion of Saint Irenaeus " If the Word became a man, it was so that man could become gods."

Other christian notables, including Clement of Alexandria, Justin Martyr, Saint Atahanasius, St. Augustine, all made statements promoting the understanding that mortal nature, being both first and necessary, would be overcome by immortality. It seems to be the case now, that there is perfect harmony between LDS doctrine and basic common orthodox christian doctrine on the possibility of immortality going forward.

There is also no debate that God experienced mortality in much the same way all other men did, learning and growing over time in wisdom and experience. Also, similar to the christian notion that Jesus emptied Himself of his divinity at the inception of his sojourn on earth, so too, in LDS doctrine, is there a veil of understanding placed upon all humans regarding their pre-mortal existence.

The only possible remaining point of disagreement could only be about the eternal divinity of God the Father. To this we can rightly point out that there is a dearth of understanding of the existence experienced by God the Father, because the Bible is silent on it. In fact, for orthodoxy to assume that while Jesus had a mortality, God the Father did not, would be to drive a large wedge between these two persons. What we do know from the bible, is that Jesus did nothing that he had not seen or known the Father to do, hence it is at least rational to believe that the Father in fact was once a man. The point being, that while Jesus Christ in practice emptied Himself of his Divinity, this does not in the mind of Christians imply there was ever a time Jesus was not God, for that would be to say that God is not eternally eternal.

Likewise, for an LDS to point to God the Father being once a man, similarly does not render Him ever uneternal. He IS by definition, eternal, notwithstanding any human experience.

In LDS writings, God the Father is indeed referred to as the "Eternal Father", and I think to make an assumption that He is anything other than eternal is counter to the teachings of the Church of Jesus Christ of Latter-day Saints.

(There are over 12 references to "Eternal Father" between the Book of Mormon and the Doctrine and Covenants alone.)

I'm new here. I see that this post has no answer by an actual LDS member, and those answers that are given are not really representative of our beliefs (due mostly to lack of familiarity with the beliefs in question). So even though this is late, I’m going to try to answer it.

First of all, we absolutely believe that God’s existence is eternal—as is the existence of all of us, and indeed just about everything that exists. Doctrine and Covenants 93:29 says “Man was also in the beginning with God. Intelligence, or the light of truth, was not created or made, neither indeed can be.” (emphasis added)

This reflects the LDS concept that there is a core part of us, called the intelligence, that God did not create and whose existence is eternal. See Abraham 3:22-25 (as well as a source I am about to quote) for more information on this concept.

Where you are confused is when we get to statements made by Joseph Smith that God the Father was not always God the Father. These ideas, as far as I know, were first presented in coherent form by Joseph in the King Follett Discourse, which he gave a few months before he died (the date is April 7, 1844). If you want to know what JS actually said about this, you can find the original text here (all right, it's not the original text, but we don't have the original text in its entirety):

First half

Second half

In your question, you're probably thinking about the following:

"God himself was once as we are now, and is an exalted man, and sits enthroned in yonder heavens! That is the great secret. If the veil were rent today, and the great God who holds this world in its orbit, and who upholds all worlds and all things by His power, was to make himself visible—I say, if you were to see him today, you would see him like a man in form—like yourselves in all the person, image, and very form as a man; for Adam was created in the very fashion, image and likeness of God, and received instruction from, and walked, talked and conversed with Him, as one man talks and communes with another."

You can take this to imply that God has a beginning, but on the whole what Joseph Smith has to say refutes that idea. The following is a quote from the sermon that is sufficient for my purposes:

“I am dwelling on the immortality of the spirit of man. Is it logical to say that the intelligence of spirits is immortal, and yet that it has a beginning? The intelligence of spirits had no beginning, neither will it have an end. That is good logic. That which has a beginning may have an end. There never was a time when there were not spirits; for they are co-equal [co-eternal] with our Father in heaven…. Intelligence is eternal and exists upon a self-existent principle. It is a spirit from age to age and there is no creation about it. All the minds and spirits that God ever sent into the world are susceptible of enlargement.

The first principles of man are self-existent with God. God himself, finding he was in the midst of spirits and glory, because he was more intelligent, saw proper to institute laws whereby the rest could have a privilege to advance like himself. The relationship we have with God places us in a situation to advance in knowledge. He has power to institute laws to instruct the weaker intelligences, that they may be exalted with Himself, so that they might have one glory upon another, and all that knowledge, power, glory, and intelligence, which is requisite in order to save them in the world of spirits.”

Here’s a summary to tie this all together. Yes, we believe that God is eternal. No, we do not believe that He was God in the sense that we know Him now during the first phase of His (eternal) existence.

A few notes at the end here. One is that President Joseph Fielding Smith explains this issue somewhat differently than I just did in Doctrines of Salvation, which is not official Church canon per se (and I don’t agree with all of it!), but it is a monumental work which touches almost every aspect of our doctrine. He argues that for us, God’s existence might as well be eternal, since this time when God was not God falls outside of our experience, and it is in that sense that the word “eternal” is used in our scriptures when referring to God. (Doctrines of Salvation, Volume 1, Chapter 1, pp 9-12)

Another thing that should be noted is that Joseph Smith never had time to really expound on and clarify these ideas very well. As I already noted, he was dead within a few months of giving that sermon. So most of the commentary that you may hear on what he actually meant is probably wrong. It is LDS doctrine that men may become “gods” after being saved, but exactly what that entails (aside from the same personal perfection that the Father and the Son possess) is not really defined. And most authoritative statements by LDS leaders have tended to shy away (perhaps deliberately?) from clearly defining it. As John says, “Beloved, now we are the sons of God, and it doth not yet appear what we shall be: but we know that, when he shall appear, we shall be like him; for we shall see him as he is.” (1 John 3:2, KJV, emphasis added)

My very last note is that the question asks "When did the LDS church start teaching that God the Father had a beginning?" with the apparent connotation that, since there was a time when the LDS church did not teach this, that we're revising our doctrine. This is true, but not in the way that (it seems to me) it's implied. We believe that although Joseph Smith restored many important ideas about our relationship with God, as well as the authority to legitimately perform actions like baptism, our understanding of true doctrine is still necessarily incomplete, and is therefore undergoing a continuous process of revision. This was even more true in Joseph Smith's time than it is now. Articles of Faith 9 states: "We believe all that God has revealed, all that He does now reveal, and we believe that He will yet reveal many great and important things pertaining to the Kingdom of God." (emphasis added)