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):
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)