During my youth I went through quite a bit of survival/backcountry-lore type training. We learned to use various twigs to clean our teeth like that. If you chew them up just right you can get a really nice "brush" as well as fibers that amount to decent floss substitutes. We didn't have miswak available though.  40 years later it's hard to recall which plants produced the best results :)