Sorghum is an african grain and is widely used in southern african beer I think. "The Homebrewer's Garden" says that beer with sorgum in it outsells beer without 7-1 in South Africa, so much so that Guinness had to adapt its recipe. I think you could easily make a decent beer from sorghum alone. You can also use amaranth, which is a nutty flavoured south american grain which was widely used by the aztecs and incas. Corn is also gluten free and could be used to add fermentables. Apparently the jury is out as to whether oats are ok for coeliacs, but if it was ok that would be a really useful body enhancing ingredient. I think you can buy oats that haven't been near any wheat or barley, from special coeliac stores. Of course you also have Spelt, which is an ancient form of wheat but which is ok for gluten intolerant folk
the homebrewer's garden has a recipe for a beer that just uses sorghum, 2.3kg sorghum malt, 227g raw sorghum, 227g millet or flaked corn, 227g sorghum syrup, and whitbread or london ale yeast. that's for only 4l so you're looking at a lot of sorghum for not too much yield it seems.
weyermann.de do spelt malt.