Rusty Edge
Deity
Or Barbarian Privateers
Btw. are there barbarian privateers? There should be. It would add flavor to the game since you wouldn't know if its an AI attacking you or just barbarians.
I have only seen one that I didn't build myself, and I'm pretty sure it came from another civ and there were no barbs left at that point.
Now that I think about it I don't remember barbs with gunpowder in BTS at all, but that could be playstyle.