Very early. At least as early as Justin Martyr, in The First Apology (~AD 150):
For they proclaim our madness to consist in this, that we give to a crucified man a place second to the unchangeable and eternal God, the Creator of all; for they do not discern the mystery that is herein, to which, as we make it plain to you, we pray you to give heed.
Theophilus of Antioch, in Book I of his writings to Autolycus (~AD 170–80):
And He is without beginning, because He is unbegotten; and He is unchangeable, because He is immortal.
Also, Tertullian, in Against Hermogenes (~AD 200):
[B]eing the Lord, He is indivisible, and unchangeable, and always the same.
Origen, around AD 235, wrote On Prayer, in which he writes:
But in the case of God, inasmuch as He is himself ever unchangeable and unalterable, the proper name which even He may be said to bear is ever one, that mentioned in Exodus, "He that is," or the like.
With respect to creeds, the AD 325 version of the Nicene Creed specifically mentions the immutability of the second person of the Trinity:
But those who say: [...] 'The Son of God is created,' or 'changeable,' or 'alterable'— they are condemned by the holy catholic and apostolic Church.
The Chalcedonian Definition (AD 451) says something similar.
When considering this question, we need to remember that:
- We don't have much in the way of early writings of the church (i.e., 2nd century)
- Early creeds were not meant to nail down every point of Christian doctrine: they were often written as responses to particular heresies, and if no heretical group challenged the immutability of God, then that phrase would be unlikely to occur in a creed.
The fact that the immutability of God is so well attested in Scripture (in addition to the excellent verses mentioned in Mike's answer, we have Exodus 3:14, Psalm 102:26–28 and Hebrews 1:11–12, among others), it seems likely that no one seriously challenged this doctrine in the early church, except in the case of Christ's nature. Therefore, there was no need to make more than passing reference to it in writings, and no need to include mention of it in the creeds.