While different Christian groups might answer this differently, the vast majority today are Chalcedonian Trinitarians. I will answer the question from that perspective.
When it is said that God does not change, this means that God's essence, His nature does not change. The Second Person of the Trinity assumed the Human nature uniting it in His Person. So in this limited sense, you can say that there was a change. However, that change was not a change in the changeless Essence of God.
At the Incarnation, the Divine Nature was united to the Human Nature in the person of Jesus Christ. However, it is a matter of faith that Divine Nature was not altered or changed by this union. From the Formula of Chalcedon:
one and the same Christ, Son, Lord, Only-begotten, recognized in two natures, without confusion, without change, without division, without separation; the distinction of natures being in no way annulled by the union, but rather the characteristics of each nature being preserved and coming together to form one person and subsistence
The divine nature is united with the human nature in person of Jesus Christ, but it is unchanged by this union.
You mention Hebrews 13:8, but this verse needs to be kept in context:
Remember those who rule over you, who have spoken the word of God to you, whose faith follow, considering the outcome of their conduct. Jesus Christ is the same yesterday, today, and forever. Do not be carried about with various and strange doctrines. For it is good that the heart be established by grace, not with foods which have not profited those who have been occupied with them. [Hebrews 13:7-9 NKJV]
Here, Christians are directed to remain in the teachings they have received and not to chase after new one. The Christian teachings remain the same. This is not a passage about the nature of Christ.