I thought it was a fun question, I gave it some thought. Layman's version, so corrections are welcome.
The very early universe, the first few seconds or so, it was quite dense. This is fairly well publicized and the specifics and details don't really matter for this question, but the energy and stuff in the early universe that later formed the Milky-way and the energy and stuff that formed Andromeda were cosmic neighbors and in the first seconds of the universe, quite close to each other. The basic Hubble rule is that things that are close (in cosmological terms) were always close, like the dots on a balloon that gets blown up. Everything moves away from everything else, but things that were next to each other were always next to each other. On smaller scales, like stars within galaxies or planets, this isn't true because of gravitational assists and different orbital paths, but its true for galaxies. (there might be some small variation on this with "orbiting" dwarf galaxies, but it's still by and large, true).
Another important point to make about the early universe is that it was much more uniform, so, because of the uniformity, gravity was pulling nearly equally in all directions. The nearby somewhat more massive clouds of matter and energy didn't dominate gravitationally because there was similar mass in all directions. You might think that a denser universe means stronger gravity in the direction of nearby matter, but that doesn't happen if the matter is spread evenly enough in all directions.
So, generally speaking, in the very young universe, the stuff that became the Milky way and the stuff that became Andromeda started out much closer, but they didn't pull each other much early on because of uniformity.
Over time, local gravity overcame uniformity. I couldn't tell you when that happened (maybe someone here can), but it took some time before the makings of galactic groups and clusters began to form. We know from the background radiation map that the Universe was still quite uniform as late as 380,000 years after the big bang. See picture:
(Edit due to correction). And at 380,000 years, the known Universe is thought to be about 1/1100th it's current radius. We know from the cosmic background radiation that at that time, the Universe was still largely uniform, though non-uniformity did lead to the formation of galaxies, clusters and super-clusters, so it was important, but it still took some time for local groups and galactic clusters to form.
On this map, the hot regions, shown in red, are 0.0002 Kelvin hotter
than the cold regions, shown in blue.
These cosmic microwave temperature fluctuations are believed to trace
fluctuations in the density of matter in the early universe, as they
were imprinted shortly after the Big Bang. This being the case, they
reveal a great deal about the early universe and the origin of
galaxies and large scale structure in the universe.
But once local gravity overtook uniformity, then galaxies can start drawing each other together more efficiently. The spiderweb pattern of galaxies shows that there is a tendency for this to happen, as galaxies draw other galaxies towards them, even as space expands, so you get lines of more dense regions with more galaxies and pockets of empty space, mostly free of galaxies.
Source of picture for further reading.
So, what basically happened with Andromeda and the Milky-way is that expansion combination with uniformity set them fairly far apart even as they were still forming, but they were still next door neighbors as far as galaxies go.
Both the Milky-way and Andromeda have absorbed smaller, closer dwarf galaxies, perhaps many times, so they weren't the closest 2, but they were the closest 2 non dwarf galaxies (at least, that we know of).
You might think that galaxies could orbit other galaxies, but the nature of Hubble expansion doesn't give galaxies much tangential velocity towards other nearby galaxies, so basically, 2 galaxies are either moving towards each other due to mutual gravity or away from each other due to expanding space. Now in a 3 or more galaxy system with similar masses, they can get some tangential velocity, but generally speaking, the direction between any 2 large galaxies is mostly either towards or away, not an orbit.
Another thing to keep in mind, once the uniformity effect is overtaken by local gravitation of local groups or clusters, is that massive objects at these distances don't exactly pull each other quickly. It takes a long time for gradual acceleration to turn into relevant velocity.
At our current distance from Andromeda (about 2.5 million light years), and it's current mass (about 1.5 trillion solar masses), it's G force on us, using the formula below (Math can be added if needed):
comes to about 1/2.8 trillionths of a meter per second squared. That's less than 1/20,000th the gravitational pull Pluto has on Earth. A pull that small is going to accelerate things towards each other extremely slowly, so (I think) for the first billion or few billion years, the expansion of space between the Milky way and Andromeda likely exceeded any gravitationally caused velocity between them.
The good news is, Andromeda and the Milky-way have had a long time to pull on each other. About 13 billion years or so. 1/2.8 trillion m/s^2 over a billion years is works out to about 11 km/s. Over 13 billion years, 143 km/s. And, the actual velocity that the Milky-way is moving towards Andromeda isn't too far away from that, about 110 km/s. That right there gives us a ballpark Netwonian estimate for how far apart they were when they started. (Now, footnote, for objects of somewhat similar mass, you have to take the mass of both of them, not just the larger one, so it's closer to 15 or 16 km/s per billion years), but that doesn't change the overall numbers too much.
Dark Energy expansion (which currently, between the Milky-way and Andromeda is about 60 km/s), and that makes the calculations a bit more tricky, especially since dark energy expansion might not have been constant throughout the last 13 billion years. Related article here.
At the current rate they are moving together, about 110 km/s or, 250,000 mph or 1/2,680 c, In one billion years at current velocity Andromeda will be 375,000 light years closer (and, in reality, a bit more as it will continue to accelerate by mutual gravity and dark energy expansion will be reduced as they get closer).
And if we work backwards, a billion years ago it was a bit less than 375,000 light-years further away than it's current 2.5 million light year distance, with diminishing distances further away over previous billion year intervals. The farther back you go, and difficulties with knowing how close they were when local gravity became a key factor over uniformity makes estimates pretty difficult, but they were probably never too much further apart than they are now. Perhaps double, as a very rough guess. Because gravitational acceleration drops off at the square of the distance, I find it hard to believe that Andromeda was ever much more than twice as far as it is now.
I would imagine, based on my assumptions above, that by the time the galaxies were recognizable as galaxies, say, when the universe was a billion or 2 billion years old (give or take), Andromeda and the Milky way were probably moving away from each other initially, but over time, the gravitational attraction was able to overcome overcome the expansion of space.