DS9 for example has relatively obscure thrusters that are used to adjust the station's orbital trajectory... I would imagine that large Federation starbases come equipped with same technology that allows for periodic adjustments to maintain orbit.
As such, I think they could be moved in the same way DS9 was moved - by projecting a subspace field around the station to lower its mass to practically nothing, and then use directional thrusters to move it where they want it to be.
As for deep space construction... hardly that it would require many trips... with replicators and transporters, all you need to do is run to the nearest solar system for harvesting all those Zettajoules of Solar energy that are flowing through the system, or just use bussard collectors that generate power continuously for the ship by gathering background radiation, and you simply convert that energy into desirable matter (replicators were described on several occasions to directly convert energy into matter and back again - as such, they have no need of 'bulk matter' as some people claim, because there's no confirmation or solid evidence they need it in the first place) which can then be auto-assembled by the computer itself. Given that ships are capable of transporting something the size of a shuttlecraft, or even bigger, construction of an actual starbase in deep-space doesn't seem like a big problem).
The self-replicating mines on DS9 were likely powered through a similar method... aka drawing power from the environment (solar, background radiation, etc.), and they also had thrusters for continuous adjustments of their positions.