How can the Vedas be constant when they come from the 4 heads of Brahma and Brahma changes every time? Vedas need to change? Isn't it?
Only Puranas may be constant.
Vedas are eternal and apauruSheya (अपौरुषेय) which means "not produced by man". Veda Samhitas (core portions of Vedas) are heard by sages in deep tapasya. Veda Samhitas talk about eternal truths which are constant always. Truth is always same and it doesn't change with time.
Vedas also say, time is cyclic and the process of creation, preservation and destruction is happening since eternity. Supreme Brahman delivers Vedas to creator Brahma at beginning of every cycle of creation.
Svetasvatara Upanishad 6.18 says
yo brahmāṇaṃ vidadhāti pūrvaṃ yo vai vedāṃś ca prahiṇoti tasmai /
taṃ ha devam ātmabuddhiprakāśaṃ mumukṣur vai śaraṇam ahaṃ prapadye // 6.18 //
Seeking Liberation, I take refuge in the Lord, the revealer of Self-Knowledge, who in the beginning created Brahma and delivered the Vedas to Him.
Puranas do mention the same but replace the supreme Brahman with Shiva or Vishnu or Devi depending on the category of Purana.
So, Brahma utters Vedas only after acquiring from Supreme Brahman.
How Vedas can be constant at all times?
Vedas or to be precise Veda Samhitas talk about Supreme truths which are same at all times. Swami Krishnananda says the following in his book Lessons on Upanishads,
We begin to feel there must be something above this world. This was what the great poets and the sages of the Vedas felt. Everything seems to be transitory, moving, and in a state of flux. There is change in nature, change in human history, change in our own mental and biological constitution, change in even the solar system, the astronomical setup of things. Everything is changing. The perception of change is something very important for us to consider. How do we know that things are changing, that things are moving or are transitory? There is a logical peculiarity, a significance and a subtlety at the back of this ability on our part to perceive change and transition in things. A thing that changes cannot perceive change by itself. Change cannot know change. Only that which does not change can know that there is change.
This is a very important point at the rock bottom of our thinking that we have to recognise. If everything is changing, who is it that is telling us that everything is changing? Are we also changing with the things that change? If that is the case, how do we come to know that all things are changing? Logical analysis of this peculiar analytical circumstance tells us that there is something in us which does not change; otherwise, we would not know that things are changing.
I have something in me which does not change, and you also have something in you that does not change. If this is the case, it seems to be everywhere. It does not mean that this unchanging so-called thing is only in one person, as all persons have an equal prerogative to conclude that something unchanging seems to be there.
The Veda Samhitas to which I have made reference –which are the outpourings of spiritual seekers, sages and masters of advanced religious thought and spiritual perfection – felt the presence everywhere of something that does not change. All things seem to be embedded with something that cannot change.
The whole universe of perception, the entire creation, may be said to be involved basically, at the root, in something which cannot be said to change. This is an adorable and most praiseworthy conclusion, and anything that is adorable is a worshipful something. These masters of the Vedas Samhitas, therefore, recognised a divinity in all things. There is a god behind every phenomenon, which is another way of saying there is an imperishable background behind every perishable phenomenon.
Veda Samhitas describe that "unchanging thing or God" which is same at all times. So, Vedas don't change with time.
Next possible question which may arise is, how it is possible to describe "unchanging thing" through something changing?
It is possible because of divine language संस्कृतम् (Sanskrit). Like Vedas, Sanskrit also do not change with time. Sanskrit doesn't evolve with time.
Sanskrit has fixed number of Dhātus (Verbal roots) by which we can guess meaning of words without help of dictionaries. Also, Sanskrit doesn't have proper nouns. Sanskrit describes objects with attributes or qualities they possess. All Sanskrit names are derived from their attributes. An attribute can refer to multiple objects. So, meaning of words in a Sanskrit sentence depends on context. Sometimes, literal interpretation of Vedic verses could be disastrous.
I have explained more about uniqueness of Sanskrit language in this answer and also refer this blog by Gurudev where author of the blog describes the uniqueness and eternity of Sanskrit language in detail.
Coming to Puranas, many events are repeated in every Manvantara. The stories mentioned in Vedas occur in every Manvantara. Different Puranas mention same stories with slight variations as every Purana narrates mainly stories of a particular Kalpa as discussed in this answer. However, only some stories repeat not all.
So, there's no rule that Puranas should be same at all times.