A few suggestions... A la Clan of the cave bear...you could chew the end of a green twig and use the fibers to clean your teeth... This summer I took a primitive skills course, and it was suggested that pine pitch/sap has antiseptic properities and was good to use for teeth cleaning i.e spruce gum...i found it rather pleasant... Also white sage can be used in this manner, chewed and the juice swished around the teeth... As for actually brushing teeth, the probably didn't do it much, and had little need...they didn't eat the sugary grains and snacks we do. Dried fruit may have been a problem...but they also had a better diet in general. More calcium, perhaps prevented tooth decay ... Good luck! As for non paleo alternatives... You can try baking soda with a touch of mint oil, or one of the more natural brands like desert essence, or tom's of maine...