What happens to photons that don't interact with something? Say a photon left one of the first stars ever created in our universe.  This photon has been traveling for 13+billion years through the vastness of space without ever hitting anything.  Sure, it's probably been tugged at by gravitational interactions, but it's still happily traveling at the speed of light without direct interaction with matter. 

As we know, most of the universe is composed of mostly empty space.  The odds of any single photon hitting something (like the Earth as starlight, etc) would seem to be very small.

What will eventually happen to this photon?  Will it eventually reach the other end of the universe, and if so, what would happen to it there?
Your statement "most of the universe is composed of mostly empty space" is very vague. In reality, the Universe is embedded in diffuse background photon fields, from low energy (like the so-called cosmic microwave background which is relic from the big bang) to very high energy (from the extreme compact objects, like AGNs). Of course, there is also unknown dark matter. It seems that dark matter probably only takes part in weak interaction. Thus, it probably won't interact with photons (the same argument with cosmic background neutrinos). The chance of photon-photon interaction and photon-electromagnetic-fields interactions depends on the energy of the photons. For high energies, it is not low as you expected. Even if a photon gets lucky and doesn't interact with the other particles, still it won't reach the edge of the Universe. The reason is that the Universe is expanding.