I've always liked the idea of a united Gaul as a European power. Without Rome, I could see the Arverni uniting Gaul around the time of Caesar's campaigns there IOTL. They would have the strong, defensible borders that the Bourbons constantly sought for France (the Rhine in the east, the Alps and the Pyrenees in the South, and the sea in the west and north); the Germanic tribes would provide enough trouble for the Gauls to develop a strong and sophisticated military.
Carthage will almost certainly not create an empire at the scale of Rome's. Carthage was a maritime empire, not a land empire. The only territory outside Africa it really fought for between 500 and 240 BC was Greek Sicily (and maybe Sardinia, I can't remember when it was colonized by Carthage); it's conquests in Iberia came primarily as compensation for the territory it lost after the First Punic War, and were won by a private army. The Carthaginian state, outside of Greek Sicily, was historically more interested in peace and prosperity than wars of expansion, and Rome being out of the picture means only that there is less incentive for expansion.
Now, that is my opinion on the Carthaginian state's interest in expansion. I suppose it is feasible that an individual like Hannibal Barca could amass enough wealth to employ a private army and form an independent Punic kingdom in Italy or Iberia or something, though it's probably unlikely. It's unlikely that it would be a state-sponsored mission, unless tribes were threatening Punic cities on an annual basis, since there would be little reason for the government to commission it otherwise. Such a kingdom would likely gain its independence from Carthage pretty quickly, considering the large reserves of manpower it would then have, and the lack of will of Carthage itself to sink large resources into subduing and administrating barbarian tribesmen. IMO, it'd be more interesting to think about how those territories might have developed without a power conquering it, whether it be Rome or Carthage or Macedonia.
The eastern Mediterranean is probably dominated by Greeks, especially if the PoD is sometime after the Macedonian victory at Chaeronea. If it's before, it's probably more likely that Persia dominates the east, whether the Achaemenid dynasty still rules or not.
One timeline the OP might be interesting in checking out is Errnge's The Weighted Scales, which begins with Rome's destruction in 390 BC at the hands of the Gaulish warlord Brennus.
