“We lost two points ... because we created more goal chances and for this reason we deserved a victory,” said Barcelona coach Gerardo Martino, whose side, like Milan, remain unbeaten in the group.
Unlike Martino, Arsenal manager Arsene Wenger would have been happy with a draw in their match at home to Dortmund because it would have kept them top of Group F.
Instead, the section was blown wide open as the Londoners, who lead the Premier League after some stylish performances and had enjoyed back-to-back European wins before this match, received a reality check.
The Germans, whose coach Juergen Klopp watched from the stands as he served a touchline ban, took a 16th-minute lead through Henrikh Mkhitaryan before Olivier Giroud equalized for the hosts before the break.
Wenger had spoken of the danger of Dortmund’s Polish players before the game and his fears were proved right when Lewandowski volleyed home eight minutes from time to snatch the points.
Meanwhile, Group G is anything but open as Atletico Madrid became the only team to still have a 100 percent record after three rounds of matches.
Costa enjoyed a dream competition debut in Vienna, scoring the second and third goals, including a superb effort after he raced from inside the Atletico half and danced past the last defender before slipping the ball into the corner of the net.
It was the other extreme for another Group G player, Herrera, whose first Champions League start lasted six minutes.
The 23-year-old Porto midfielder was shown his first yellow card after a foul and then picked up a second booking for encroaching on the free-kick he had just given away to set a red-card record he will want to forget.
The hosts almost managed to hang on for a draw before an 86th-minute header from Aleksandr Kerzhakov stole the points for Zenit, with the salt in the wound coming from the fact that ex-Porto forward Hulk had set up the goal.