Don't discount aberrations... In my setting, there are these delicious little hopping critters called pit leeches. Better than chicken. : ) I imagine rust monsters are a bit like crab, and that debauched nobles in a distant land somewhere could have taste for chilled mind flayer brains with a dash of nutmeg.
To be honest, Agback's idea of stone to flesh, as revolting as it is

, is something I've thought about. I imagine it would keep someone alive in a pinch.
Aside from fungi, there are protists like algae (if there are trees, why not algae?), which can be dried and used as flour, combined with monerans like certain yeasts to make 'deepbread'- or to thicken stews. This would also explain the dwarven love of ale... the ingredients for bread are also good ingredients for booze. Lichens (near cave openings) can fill a similar role. Bats, striges, grubs, worms, various creature eggs, and the occasional large creature can help to round out the diet.
Based on bat guano alone, fungi are justified, but if deep-dwellers also catch largely inedible fish and other creatures, these can be used as fertilizer. Over
the generations, the underdark could become very fertile. This isn't even accounting for magic, per se.
Edit: Excellent thread, BTW...