  Models of non-interacting fermions coupled to auxilliary classical degrees of
freedom are relevant to the understanding of a wide variety of problems in many
body physics, {\it e.g.} the description of manganites, diluted magnetic
semiconductors or strongly interacting electrons on lattices. Monte Carlo
sampling over the classical fields is a powerful, yet notoriously challenging,
method for this class of problems -- it requires the solution of the fermion
problem for each classical field configuration. Conventional Monte Carlo
methods minimally utilize the information content of these solutions by
extracting single temperature properties. We present a flat-histogram Monte
Carlo algorithm that simulates a novel statistical ensemble which allows to
acquire the full thermodynamic information, {\it i.e.} the partition function
at all temperatures, of sampled classical configurations.
