Look up the Walstad method of planted tanks. Basically a method using soil under your substrate to promote great plant growth. Animal waste then disintegrates through the substrate into the soil, keeping it nutrient rich, and stopping it from fouling the water. I'd suggest 1 inch of soil, with the thinnest possible layer of sand on top, just to keep the soil from floating up. You should plant this tank extremely densely from the very beginning to prevent algae blooms and nutrient build up from the soil. It is tough at first, but once a set up like this is established, the only maintenance it needs is water top ups, and just an air stone to provide mild circulation. No more gravel vaccums and big water changes! PM me if you want to know how I prepared the soil for my tank, as this can make or break your Walstad.
As for live food, mature tanks contain a whole selection of small creatures. I don't know about any breeding in your tank enough to keep a newt well fed, but I do know they feed on my colony of pond snails, because I keep seeing many tiny ones but never any past a certain size. A colony of red cherry shrimp will also provide an occasional snack, though they are too fast to catch most of the time. You can leave blackworms, tubifex and bloodworms in the tank in small numbers as well, the newts are capable of hunting them at their leisure. However I don't think any co-habitant live food will ever match up to a good earthworm in terms of nutrition, and I suggest that you keep them on earthworms as a staple.
My trio are very happy. 
