There are several aspects to the problem. First of all: there are no mechanisms in the present day astrophysics that could considerably change the velocity of such a large and rather diffuse object as galaxy. The only way that could be done is by a very large gravitational anomaly (concentration of mass), but even the Great Attractor is only capable of relatively minor change in velocity ($\pm 700\,\text{km}/\text{s}$).
So a potentially relativistic galaxy must have the origin of its current velocity going back to a much earlier cosmological epoch.
Another aspect of the problem is that a massive relativistic object moving in expanding universe for a cosmologically long time would be losing its energy with the universe expansion. We assume that velocities and energies are measured with respect to a suitably chosen frame of reference, for example the frame associated with cosmic microwave background radiation.
If at moments $t_1$ and $t_2$ the velocities of an object are $v_1$ and $v_2$ respectively, they would be connected to the cosmic scale factor of the universe $a_1$, $a_2$ at $t_1$ and $t_2$ by a relation:
$$
\frac{\gamma_2 v_2}{\gamma_1 v_1}=\frac{\left(1-\frac{v_2^2}{c^2}\right)^{-\frac12} v_2}{\left(1-\frac{v_1^2}{c^2}\right)^{-\frac12}v_1} = \frac{a_1}{a_2},
$$
where $\gamma_{1,2}$ are relativistic factors. We see, that weakly relativistic objects would lose about half their velocity while universe doubles in size while ultrarelativistic objects would lose half its energy at the same time.
So for a galaxy to be even weakly relativistic today it had to be ultrarelativistic at the time of its formation.
The lack of large velocity anomalies in galaxies at earlier cosmological epoch could be seen as a part of the homogeneity (or horizon) problem in cosmology: Why the variations in the velocities of galaxies are so small across the whole observable universe? The most popular solution for this problem is cosmic inflation. If there was a phase of rapid growth during which the scale factor increased by a factor of about $10^{26}$ whatever inhomogeneities were there at the beginning, they became too 'diluted' to produce a measurable variations today.
As for a smaller scale relativistic objects, the processes around black holes could potentially provide large enough velocities. For example recoil during black hole mergers could provide 'kick' velocity of a several thousand km/s. And if one of merging black holes had stars (or smaller bodies) orbiting it those bodies could be ejected with velocities of up to one third the speed of light:
The potential for observation of such objects is discussed in:
- Loeb, A., & Guillochon, J. (2014). Observational cosmology with semi-relativistic stars. arXiv.
As for your neutrino question:
Same question applies in the other direction, if neutrinos have a mass, is the Earth in a special (instantaneous) frame where some neutrinos are completely still?
For the neutrino to currently have a velocity comparable to that of the Earth it must be emitted at the very early cosmological epoch. Such relic neutrinos constitute the cosmic neutrino background. This background radiation would provide its own reference frame (close to the frame of CMBR). In it relic neutrinos would have an isotropic velocity distribution with the peak determined by the actual value of neutrino rest mass. For example assuming the mass of $0.1\,\text{eV}$ the peak of velocity would be at about $1500\,\text{km/s}$. So yes, some small fraction of relic neutrinos would have velocities close to zero in the Earth frame of reference.
