Cool.
So to start, I agree that in general batteries suck and should be avoided for home component use. The one place I *may* take that back is in your phono-stage. The phono-stage has a LOT of gain, and has to work with insanely small signals. Because of these 2 things noise in the power supply is often a more serious problem with phono-stages than with pretty much anything else at home. You can work around these issues, but it will add to the complexity & expense of something that is already pretty complex and expensive...
So, I would say, dont shy away from batteries. This will open the doors to many options especially to "get your foot in the door." Many designs can be modified to take wall-power at a later date if you want, but a set of 9V batteries lasts incredibly long in most of the simpler DIY phono stages. I would still lean towards rechargeables, but there are options.
RJM has a couple cool phono stage designs. I am biased towards his "passive" one, as I prefer passive RIAA.
Hagerman has the ever popular Bugle.
If you look around on the internet you can find a schematic of the Grado phono stage.
There are lots of options.