The speed of light is a defined constant so cannot vary - or at least it's variation cannot be measured since it is used to define the measurement system. However $c^2 = (\mu_0 \epsilon_0)^{-1}$ and so both $\mu_0$ and $\epsilon_0$ could vary in opposite directions.
If $\epsilon_0$ varied then this would fundamentally change the spectrum due to the various transitions in any given element. For example, the energy levels of a hydrogen atom are
$$E_n = \frac{m_e e^4}{8h^2 \epsilon_0^2 n^2}\ , $$
where all the symbols for the fundamental constants are conventional. If $\epsilon_0$ changed, this would mean the separation between energy levels and hence the intrinsic frequency/wavelength of the associated spectral line would change. But all the spectral lines would change their wavelengths by the same factor, so this isn't diagnostically useful and would just lead to a different redshift measurement.
Further, a variation in $\epsilon_0$ could be disguised by a variation in $h, e$ or $m_e$ and so we arrive at a fundamental issue that the only "constants" it is meaningful to discuss the variation of, in either time or space, are the fundamental dimensionless (i.e. they don't have units) constants like the fine structure constant.
However, there is physics and diagnostically observable consequences that are sensitive to a variation in the fine structure constant. For example, the fine-structure (spin-orbit) splitting between transitions with the same principle quantum numbers does depend on the fine structure constant and can be measured in distant galaxies.
People have been trying to constrain such variations, either by measuring the separations of various atomic transitions in distant galaxies or by looking at the history of radioactive decay in geological uranium deposits (see here for a summary). The evidence at present suggests there may be some variation at the level of about 1 part in a million on geological timescales or looking back to redshifts of 3 (corresponding to around 10 billion years in the past). The results are still under debate.
These levels of variation would have no impact whatsoever on the interpretation of cosmological redshift.