Hmm, this is just brainstorming. But Barbarians usually like their physical shows of strength or achievements. For example. This tribe's first leader slew this legendary creature. So it is called the Frostclaw clan. Or the Ironfist village. Or something the entire clan once felt strong about. Winterglave clan. Jak's Truimph.

I think if you find something where they honoured strength or felt united in, it might make it easier.

Hope that helps