Benteke followed in his own saved penalty to head home after Gabriel Agbonlahor was clumsily brought down in the box by Wojciech Szczesny, cancelling out Olivier Giroud's sixth-minute opener in the process.
Laurent Koscielny then also fouled Agbonlahor to gift another the visitors another spot-kick, which Benteke converted first time.
And Luna then wrapped things up with a cool finish on the break deep into the second half.
The result represents a dream start for a Villa side who spent long periods of last season battling against relegation, while Arsenal's chances received an early blow.
Much had been made of Arsene Wenger's reluctance to sign new stars following a close-season clearout at the Emirates Stadium, and the threadbare nature of the Arsenal squad was perhaps underlined by the presence of youngsters Emmanuel Frimpong, Serge Gnabry and Carl Jenkinson on the bench.
Santi Cazorla started the game alongside them due to his lack of fitness, though Jack Wilshere earned a starting berth for the hosts.
In the opposite dugout, Paul Lambert handed a start to just one of his close-season signings - Spanish full-back Luna - in a team similar to that which had narrowly escaped relegation last term.
And the visiting supporters' concerns regarding another battle against the drop were hardly eased when Giroud opened the scoring with just six minutes on the clock.
Alex Oxlade-Chamberlain had little trouble in escaping the attentions of Matthew Lowton down the left-hand side before cutting into the box to provide the Frenchman with a tap-in he could not miss.
Villa's day then went from bad to worse just 10 minutes later, when Nathan Baker was forced off with an injury and had to be replaced by Ciaran Clark.
The visitors could have collapsed after receiving those early blows, but Lambert's men evidenced their resolve - and they had their rewards not long after courtesy of an incredible Agbonlanhor run.
The Englishman slalomed beyond a static Arsenal defence after picking the ball up in a deep position and tempted Szczesny into bringing him down in the box. The Pole was perhaps fortunate to only see yellow but he received no such luck when his fine save from Benteke's penalty looped up perfectly for the Villa striker to nod the ball home.
Szczesny then elected to go on an unwise foray out of his box a few moments later which resulted in a hashed clearance and saw him only avoid conceding by virtue of a full-stretch save.
But Arsenal held firm against the resulting corner and a string of Villa counter-attacks to go in at the break level, a scoreline that did not please the frustrated home support.
With Kieran Gibbs having already been forced off with a cut above the eye, Wenger was forced to again turn to his bench at half-time to introduce Cazorla in place of the injured Oxlade-Chamberlain. The Spaniard's involvement did little to change the flow of the game, though, with Villa continuing to threaten and even hitting the inside of the post via a long-distance Fabian Delph strike.
They had the opportunity to take a deserved lead on the hour mark, as Koscielny's challenge on a breaking Agbonlahor in the box was, perhaps unjustly, adjudged to have been a foul. Benteke again stepped up to take the spot-kick, and he did not need a rebound this time as he sent Szczesny the wrong way to put Villa 2-1 up.
Wenger's woes were then compounded when Koscielny unwisely lunged into a challenge with Andreas Weimann to receive a second yellow card.
But there was still time for yet more disappointment, as a fantastic throughball from Weimann allowed Luna to burst beyond the Arsenal defence and pass the ball home beyond Szczesny.
