The Barbarian's name is "Hadden" and he is a very rare spawn near the Lake in Qeynos hills. Either that, or he takes a long time to respawn, since he is seldom there.

Be warned that the faction hit you take from killing him is VERY heavy. He also does not always have the Fishbone Earring, compounding the problem. The person I talked to who did kill him, said it took 3-4 times to get the earring, and many Merchants will still not sell to him.

FYI the Fisbone Earring is a moderately useful item that grants unlimited water breating and +3 Dex. In my opinion, until there is another way to obtain this item, I would try and buy it from someone, rather than try for it myself. Obviously, though, most people will not want to part with it once they get it ;-( Expect to pay a premium price...