How did the four living creatures become associated with the Gospel writers? The visions of Ezekiel recorded in Ezekiel 1 and that of John in Revelation 4:7 include four living creatures (ζῷα) that stand in the presence of the throne of God. In both visions these heavenly creatures appear like an ox, a lion, a man, and an eagle, though their detailed descriptions vary. 

Later, these four creatures – an angelic ox, lion, man, and eagle – became associated with the traditionally held writers of the four Gospels of Jesus Christ, for example by Rabanus Maurus Magnentius and in the Book of Kells, both c. AD 800, with ample other examples in Christian art even as late as the modern age.

When and how did these four heavenly creatures become symbolic representations within Christianity of the persons of Matthew, Mark, Luke, and John?
This connection was made by fathers as early as Irenaeus (d. 202).  Here's a table showing the views of several fathers whose writings we have on this subject:


                      Lion       Ox        Man          Eagle  
Irenaeus (d. 202)     John       Luke      Matthew      Mark
Victorinus (d. 303)   Mark       Luke      Matthew      John
Jerome (d. 420)       Mark       Luke      Matthew      John
Augustine (d. 430)    Matthew    Luke      Mark         John
   

A number of church fathers saw a lot of symbolism in Scripture, particularly in Revelation.  Irenaeus first connects the four creatures to aspects of Christ's life and ministry: 


  For, [as the Scripture] says, “The first living creature was like a lion,” symbolizing His effectual working, His leadership, and royal power; the second [living creature] was like a calf, signifying [His] sacrificial and sacerdotal order; but “the third had, as it were, the face as of a man,”—an evident description of His advent as a human being; “the fourth was like a flying eagle,” pointing out the gift of the Spirit hovering with His wings over the Church. And therefore the Gospels are in accord with these things, among which Christ Jesus is seated. (Against Heresies, 3.11.8)


He then connects each animal, and its christological association, to the emphases of the gospel writers:


Lion – John ("John relates His original, effectual, and glorious generation from the Father")
Ox – Luke ("that according to Luke, taking up [His] priestly character")
Man – Matthew ("Matthew, again, relates His generation as a man")
Eagle – Mark ("Mark [...] commences with [a reference to] the prophetical spirit coming down from on high to men")


Subsequent fathers took similar approaches, but often came to different conclusions regarding the specific associations.  For example, Victorinus, and Jerome following him, saw the ox and the man similarly, but swapped the other two:


  The living creature like to a lion designates Mark, in whom is heard the voice of the lion roaring in the desert. And in the figure of a man, Matthew strives to declare to us the genealogy of Mary, from whom Christ took flesh. [...] Luke, in narrating the priesthood of Zacharias as he offers a sacrifice for the people, and the angel that appears to him with respect of the priesthood, and the victim in the same description bore the likeness of a calf. John the evangelist, like to an eagle hastening on uplifted wings to greater heights, argues about the Word of God. (Commentary on the Apocalypse)


Augustine's views are found in his Harmony of the Gospels, where he disagrees with these interpretations, particularly that of Irenaeus:


  It also appears to me, that of the various parties who have interpreted the living creatures in the Apocalypse as significant of the four evangelists, those who have taken the lion to point to Matthew, the man to Mark, the calf to Luke, and the eagle to John, have made a more reasonable application of the figures than those who have assigned the man to Matthew, the eagle to Mark, and the lion to John.