In a lovely bit of synchronicity my daughter and I were just looking at a
book about sharks and there was a picture in it of a tatooing tool made of a
sharks tooth set into the end of a piece of wood much like an axe head would
be set. There's no reason why landlocked peoples couldn't use animal teeth
and/or claws for similar purposes.
Oliver