Do your aliens have to be made of matter?
Consider first an artificial intelligence - a computer program that thinks and is aware. It is pure information. It can be transmitted from one computer to another, and it would think of this process as 'travel'. An AI could simply broadcast itself out into the universe, in the hopes that some distant lifeform would one day receive the signal, realise it is a computer program, and run it to see what it does.
Now consider what would happen if you had an AI running on a quantum computer. Quantum computers operate by entanglement. If you link n particles together that can each exist in 2 states (called qubits), then it acts like a set of $2^n$ computers in parallel universes all running the program simultaneously, so it has $2^n$ times the computational power of an ordinary computer. If $n$ is more than about 300, that's more ordinary computers than can be fitted into the observable universe. And there's no reason in physics why you couldn't hook up billions of qubits. Pretty smart!
And if these qubits are distributed across vast distances, the entanglement between them remains, and they continue to act like a single coordinated entity. 209
The different parts of its mind cannot convey information from one part to another, but where they need to make a decision, they can ensure that each part of it makes the same decision. If their forces from planet X attack your left flank, their forces from planet Y will attack your right flank in perfect coordination, even though there is no way for the message to get from X to Y in time. They don't travel vast distances across the galaxy because they don't have to - they are already there! They occupy many different places at once. They occupy many different parallel universes at once! And with their vast computing power, they can create many artificial virtual-reality worlds internally, which they can explore.
It has even been seriously suggested that our own entire universe might actually be a simulated world running in some alien's quantum computer. There's no way we could tell the difference from the inside. And that would mean that we are software, too. Such aliens might sometimes pop down into the computer to talk to us, like we talk to AIs living in our computers.
By the way, it's not just electrons that can be entangled. Any particle can. That includes photons, neutrons, protons, entire atoms, and even tiny rods of silicon consisting of billions of atoms. 209