Walstad tanks are wonderful if you do them right. My first advice would be to get Diane Walstad's book, Ecology and the Planted Aquarium, and read it carefully. She is a microbiologist by training, and if you find the book interesting, you might be nerdy enough to follow her method.
You'll also learn a ton about how aquariums work. I find it fascinating, but it reads like a college level textbook. A riveting novel it ain't.
I've done many tanks using her philosophy, and all of my current tanks are Walstad setups, especially the 55g (see link in my signature) The goal is to replicate natural processes as closely as possible, eliminating unneeded technology so natural systems can do the work. The foundations of the method are roughly as follows:
1. Here's the big one: It's all about the plants, because they provide the filtration. If a Walstad setup has a filter at all, it is mostly to provide water circulation and possibly mechanical filtration. But the plants are doing the heavy lifting, keeping the water clean. In practical terms, that means you need a lot of plants, and you emphasize giving them what they need to be happy. This takes precedence over aesthetics (which can still be beautiful) and fish choices. The emphasis is on building a great habitat, which will in turn support the fish.
I usually start out a walstad tank with around 15 different species of plants, a mix of forms and growth rate--rooted, rhizome, stems, and especially floaters, knowing that over time some will come to dominate and others will die out. Once the plants are in and most of them are growing actively, you can go ahead and add fish and the plants will take care of the rest. Search "silent cycle" on the forum for lots of good info on getting started.
2. Fairly light stocking. I use aquadvisor.com to plan most of my initial stocking, and I find that keeping the stocking level around 80% or less works well for a Walstad tank. If you keep up on your water changes you can go a little over that.
3. Water circulation. In a small tank, say 30g of less, an airstone will give you all the water movement your plants need (note that some fish prefer or even require more movement that this, so do your research) In a really large tank like my 150g, I use a canister filter and a powerhead to really keep the water moving and avoid dead spots.
4. Soil substrate capped with sand. This is less important. The soil releases small amounts of ammonia and quite a lot of natural CO2, and provides a huge nutrient boost, all of which gives the plants a great start. It basically saves you the trouble of adding ammonia to cycle. That said, I've done a couple of Walstad tanks with just sand, no soil. It seems to work almost as well and doesn't have the risks of adding soil to your tank. As long as you have a good light, most plants don't seem to care too much.
As far as specific plants, you can use just about anything that isn't too fussy. I've had great results with crypts, java fern, willow and java mosses, fast growers like ambulia and valisneria, and floaters like frogbit and Asian floating fern. Like I said, add a ton of biodiversity to hedge your bets.
OK, that's probably more than enough for now. Keep us posted and good luck.
