Does Fermat's principle allow for variable refractions?
Yes, and a common example is how light from the sky can bend to run through a layer of hot air right over hot sand, causing a mirage.
However Fermat's principle is a local rule. That is, there should be no way to improve the path by adjusting it a little bit, but it might not be a global minimum. The classic example demonstrating this is a mirror. The light bouncing off the mirror often had a shorter path available (just go directly there), but there was no local variant of the path which was better than the one that it took.
Fermat's principle holds for different things for different reasons. For instance light follows the principle because of how the wave front expands. Ants follow the principle because ants that followed a faster path tend to lay a fresher scent trail. But my other comments remain true regardless of why it holds for any particular type of thing.
Yes, and that's where is gets interesting! Light will take a curved path through a tank of salt water, because the salinity, and through that the index of refraction, will not be constant but will be a continuous function of the depth.