I'm not sure how unfancy and shitty you want to go, but if you can find an older frame with horizontal drops, caliper brakes, and 27" wheels, those might be candidates. Swapping out the 27" wheels for 700c can get you enough room to run cyclocross knobbies. I have a friend who did this (single speed) and it worked fine for him.
Maybe like this:
http://seattle.craigslist.org/est/bik/1369064755.html
A "hybrid" frame might also do the trick, lots of 700c/canti brake/fat tires on those. Finding one with horizontal dropouts will be tough, though.