I dunno about 'inexpensive'. You need a very solid, twice-as-wide-as-the-wall, beyond-frostline-deep FOOTING for stone or masonry walls. Normally this would be poured concrete. That is not easy or cheap. If you have vast amounts of stone or concrete rubble, some people would do it using that instead (on a well-drained site); which cuts the cost but not the labor.
Also, please do not be offended by my asking, but, have you done any wall-sized masonry before? If not, will you at least get a *couple* good books, read every word twice, and not freelance/improvise beyond it? Because, stone or brick walls can be quite DANGEROUS when built by amateurs. There is a lot more to it than 'you stack em up so they don't fall over while you're building it', and a 5' masonry wall falling on a person, or even just chickens, is not going to be a good thing. I've seen some scary things in real life and some scary things proposed on BYC, so, I just want to make sure whether you know full well what you're doing from a craftsmanship and engineering standpoint, you know?
A single stone wall will be COLD. A double wall with rubble infill, somewhat less so. You will almost certainly need to apply plywood (preferably with insulation behind it) on the inside walls, to avoid a pathologically damp coop for several months in late winter and spring when condensation is an issue. Stone or masonry buildings can certainly be adapted to chickens, but I'm not sure it's a smart thing to BUILD just for them.
If you want inexpensive, read up on cordwood building. Or strawbale (not just 'i stacked some bales together and propped a roof on', but proper structural strawbale construction, with stucco and rebar and all that). Both will be much more functional, and both can be made about as cheaply. (They will still need a foundation though)
Good luck, have fun,
Pat