So the first question here is whether the phrase “in the beginning” means anything if God has no beginning (in particular what does it mean to say that Jesus was with the Father in the beginning). In fact this is a common atheist challenge to the idea of an uncaused God. If God always existed then how could there be a point when God decides to create the universe? Their argument is basically that this idea of an uncaused God means an always existing God for an infinite period of time and that this incoherent for a God who makes decisions and takes actions.
The traditional solution to this problem is to make God timeless and unchanging, though how this solves the problem of God making decisions and doing things is unclear. But I think this addition to a list of things God cannot do is even more troubling.
The changing understanding of time in science, however, introduces another possibility. For science no longer believes in absolute time. Instead time is simply one of the degrees of freedom in a geometrical structure of space-time which is the physical universe. Time is simply an ordering of events in a causally linked manner.
This changes things in theology because it is no longer simply a question of whether God is inside or outside of absolute time. God can be outside the temporal ordering of the physical universe but still have temporal ordering of His own personal events apart from that. Furthermore that temporal ordering is totally subject to God’s desire, and thus time becomes something which God can use as He chooses instead of being trapped in an eternity with a past about which we can ask what is He doing. Instead God can indeed have a first thought and follow that thought with others and with decisions in a temporal ordering of His own choosing and according to the modern understanding of time, it makes no sense to ask what God was doing before that, because there is no before, only God before He used time.
The upshot here is that the phrase “in the beginning” does have meaning in such a context. And when we say that Jesus was with the Father in the beginning, it mean He was there when God had that first thought in His own personal temporal sequence of events. He was there when God decided to create the angels and He was there when God decided to create the physical universe.