FRANKS!!! (which you called by the older name, Gauls).
CHARLEMAGNE! Sorry, just thought that always was my favorite historic figure, followed by augustus caesar.
@Hectate, they did eventually conquere the romans. For example, the ottoman empire (meh) took out the east (byzantine) empire, taking the capital of Constantinople. The franks were probably the most powerful, and the most successful leader, Charlemagne, was actually crowned empire of the holy roman empire or something by the pope.
The carthigians would be interesting, since they lasted a long time inside enemy territory and could have defeated the romans if they had recieved the reinforcments they needed. I don't recall much about british though...
The huns would have been quite powerful, and brutal...