$\epsilon_0$ and $\mu_0$ appear in electrostatics and magnetostatics. When we include time varying fields we have electrodynamics and the appearance of c which turns out to be related to $\epsilon_0$ and $\mu_0$.
My question is: is there an intuitive way to understand why although $\epsilon_0$ and $\mu_0$ are associated with non-time-varying phenomenas, yet they are related to c which appear when we have time varying fields.
The best way to understand this is through relativity. Magnetic fields are not constant anything--- they are not really static. They appear when charges are moving. This relates the two constants $\epsilon_0$ and $\mu_0$ by the following argument:
Consider two charged parallel lines. They repel electrostatically by an amount determined by the field of a charged line at distance r from the center: $\rho\over 2\pi \epsilon_0 r$, so they get pushed apart by a force f per unit length which is equal to:
$$f_E = {\rho^2 \over 2\pi \epsilon_0 R}$$
Where R is their separation. This force is repulsive.
If you look at the same wires in a frame moving in the direction of the wire, the electric field is still static, $E={\rho'\over 2\pi \epsilon_0 r}$, where $\rho'$ is the boosted charge density, while there is now a static magnetic field given by Ampere's law $\mu_0 \rho' v \over 2\pi r$, and this creates a magnetic force by the Lorentz force:
$$ f_B = {\mu_0 \rho'^2 \over 2\pi R} v^2 $$.
And this force is attractive.
The electric and magnetic forces have to cancel as the speed of your frame approaches the speed of light, in order for the total motion to slow down as required by relativistic time dilation. This means that at v=c, the two forces must be equal and opposite, so that
$$ \mu_0 c^2 - {1\over\epsilon_0} = 0$$
So that the relation follows from relativity. Historically, of course, relativity came after.
In order to answer your question, let's follow the derivation of the electromagnetic wave equations in reverse from the final wave equations describing the propagation of electromagnetic waves to the Maxwell equations from which they are derived.
At the end of the derivation one indeed sees how ϵ0 and μ0 end up appearing where one normally expects the square of wave's speed:
\begin{equation} \nabla^2 {\bf E} = \frac{1}{c^2} \frac{\partial^2 {\bf B}}{\partial^2 t} = \mu_0 \epsilon_0 \frac{\partial^2 {\bf B}}{\partial^2 t} \end{equation} \begin{equation} \nabla^2 {\bf E} = \frac{1}{c^2} \frac{\partial^2 {\bf E}}{\partial^2 t} = \mu_0 \epsilon_0 \frac{\partial^2 {\bf E}}{\partial^2 t} \end{equation}
This shows how the speed of light in vacuum is related to ϵ0 and μ0.
Going back, the derivation starts from the Maxwell equations, taken here in the absence of free charges and electric currents:
\begin{equation} \nabla \cdot {\bf E} = 0 \end{equation} \begin{equation} \nabla \cdot {\bf B} = 0 \end{equation} \begin{equation} \nabla \times {\bf E} = - \frac{\partial {\bf B}}{\partial t} \end{equation} \begin{equation} \nabla \times {\bf B} = \mu_0 \epsilon_0 \frac{\partial {\bf E}}{\partial t} \end{equation}
(Note that by going from magnetic B field to H field you can make μ0 disappear from the fourth and appear in the third equation.)
This shows that it isn't entirely correct to say that ϵ0 and μ0 are associated with non-time-varying phenomena only: ϵ0 and μ0 do participate in the description of a time-varying phenomenon, namely how the curl of one field depends on the rate of change of the other field.
If you write down Maxwell's equations in their full form without excluding free charges and currents, they'll look like this:
\begin{equation} \nabla \cdot {\bf E} = \frac{\rho}{\epsilon_0} \end{equation} \begin{equation} \nabla \cdot {\bf B} = 0 \end{equation} \begin{equation} \nabla \times {\bf E} = - \frac{\partial {\bf B}}{\partial t} \end{equation} \begin{equation} \nabla \times {\bf B} = \mu_0 {\bf J} + \mu_0 \epsilon_0 \frac{\partial {\bf E}}{\partial t} \end{equation}
The two extra appearances of ϵ0 and μ0 are not related to electromagnetic waves (as the derivation of the wave equations assumes they're zeroed out) and are actually what you have alluded to in your question, i.e. that the constants are primarily known from electrostatics and magnetism. As you can see they are involved in more than that including time-varying phenomena related to how time variation in one of the two fields generates the other.
In addition to Ron Maimon's answer it is worth to mention that if you consider Maxwell equations in CGS system, $\varepsilon_0$ and $\mu_0$ do not come into those equations at all. Only speed of light does. Technically, these values are constants to describe relation between historically introduced units of (that time not connected) magnetic and electric field. There is no physics in these values themselves, only their product which is equal to $1/c^2$ is meaningful.
Yes, but what is a magnetic field? It's an electric field that's changing. What is an electric field? It's a magnetic field that's changing. They are already linked to each other dynamically. The existence of one is equivalent to a variation in the other.
Magnetism is already a relativistic effect of electricity, nothing more. The two are already interlinked, and linked with the speed of light, and with relativity, even without mentioning Einstein.
