My toothpaste is made from natural materials (mainly clay, small quantities of herb extracts and essential oils) and comes in a (recyclable) aluminium tube. The cap is from recyclable plastic (but of course for plastics, "recycling" means downcycling).
I find this toothpaste marvellous and pretty sustainable (except for the plastic cap). The clay part really helps get the teeth clean. Diligent brushing even removes discolouring (coffee, tea, etc.), if only over a course of weeks/months. (By the way, this is not a crackpot health product. Clay is also found in many conventional non-natural toothpastes.)
I have used tooth powder, but not for long. (I prefer my natural tooth paste.)
So rather than looking for alternatives to toothpaste, I recommend you also look at the range of natural toothpastes.
(I use mostly Weleda toothpaste. The red and yellow types are the ones with clay; the green and blue one are tooth gels, which I didn't find as effective. Weleda should be available in many parts of the world. I have also used other natural toothpastes containing clay, whose name I don't recall, but you should take a look in your local natural health product store.)