You could just pump air down.
Harness some oxen up to a really big bellows and constantly push fresh clean air down through specially cut channels, or even through tubes made of wire and oil cloth.
The bellows could be as big as you'd like, and if you had several large bellows working in series you could keep the air flowing constantly.
Ville Niemi's answer of having ventilation shafts letting cool air down and furnaces lifting hot air up is probably best for the established areas of the mine, but in new passages where ventilation hasn't been dug you'd want to have a way to push good air in reliably.
For very deep mines, you have to watch out for auto compression (air heats up when it is compressed, and dropping deep into a mine will compress it, causing you to get negative cooling from the air), meaning that airflow should be kept to just what is needed to remove dust and gasses in those cases. Just something to consider.
So, your biggest problem is not going to be bad air. It is going to be cooling.
The temperature of a mine rises 25 °C per km of depth (1 °F per 70 feet of depth). Add to that the problem of auto compression, which you'll face in either a forced air system or naturally circulated system, and it is going to be hot once you go down a ways.
The bellows wouldn't have to be excessively big, because the more air you push down, the hotter it will get. Meaning you only want just enough to keep the bad air down and help manage the mining dust.
Refrigeration accounts for about half of the energy usage in modern day mines, and while there are some low power methods, like ice cooling, you have to have access to ice.
There might be other ways, depending on where your mine is.
For instance, if your mine is high in the mountains, then it could be really really deep, and still have drainage for an underground river, which could be used as a heat sink, and could allow for ventilation too.
Another way would be to have stages, with another set of bellows every half KM down, and another set of bellows where air is drawn back up with a reverse bellows; hook the air intake on the bellows to an air duct deep in the mine, and every time it blows to a higher stage it will draw air up from below.
The de-compression and low pressure caused by this would cool the air down below, and hopefully balance out the auto compression, while also helping pull heavier bad air out.