Two Gareth Barry penalties and a fight between Kieron Dyer and Lee Bowyer sent eight-man Newcastle crashing to defeat.
Juan Pablo Angel made the most of a defensive mix-up to put Villa ahead after five minutes with a low drive.
Barry added a second from the spot after Stephen Taylor was sent off for deliberate handball in the 73rd minute.
Stephen Carr's foul in the box led to Villa's third before Dyer and Bowyer were red-carded for their punch-up as tensions ran high at St James' Park.
It was a miserable end to a Premiership clash which had looked so promising for Newcastle.
After Alan Shearer's decision this week to postpone his retirement, the talismanic striker was greeted by a hero's welcome at St James' Park.
But celebrations among the home crowd were shortlived as Villa stunned their hosts just minutes after kick-off.
Angel was teed up in the box after poor defending from Jean-Alain Boumsong and calmly sent home a low shot.
Newcastle quickly shook off their surprise and went on the offensive with a bevvy of chances before the break.
Shearer had a header on goal, Bowyer's close-range snapshot was blocked and Jermaine Jenas' effort went over the crossbar as the equaliser eluded the Magpies.
At the other end, the visitors nearly doubled their lead when Barry hit the post with a right-footed shot, while Jenas wasted another chance for Newcastle in the dying seconds of the first half with poor finishing.
With around 15 minutes to go, Villa finally extended their lead when Darius Vassell dispossessed Nicky Butt at the halfway line and raced through on the goal.
After skipping past the keeper, the England international saw his shot blocked substitute Taylor's hand.
Taylor was subsequently sent off before Barry made no mistake from the penalty spot.
Barry then piled on the misery for Graeme Souness' side when he claimed another after Stephen Carr's bodycheck on Vassell on the edge of the box.
Newcastle's dreadful afternoon ended in disgrace when Bowyer and Dyer traded punches with each other in an astonishing bust-up and were both sent off to leave their side down to eight men.
Aston Villa manager David O'Leary:
"We were the best team by a mile and we deserved to win. We won two penalties because we created clear situations and the ref had no choice," said O'Leary.
"It was nice to get all our players fit. Juan Pablo Angel and Darius Vassell have not played together this season and they were big pluses for us.
"They had a disputed penalty but it's the only thing they can argue about."
Newcastle: Given, Carr, Boumsong, Andrew O'Brien (Taylor 52), Hughes, Jenas (Ameobi 63), Butt, Bowyer, Robert (Faye 84), Shearer, Dyer.
Subs Not Used: Harper, Milner.
Sent Off: Taylor (73), Bowyer (82), Dyer (82).
Aston Villa: Sorensen, Delaney, Mellberg (Ridgewell 45), Laursen, Samuel, Hendrie (Solano 84), Davis, Hitzlsperger, Barry, Angel (Cole 88), Vassell.
Subs Not Used: Postma, Berson.
Booked: Hitzlsperger, Mellberg.
Goals: Angel 5, Barry 73 pen, 80 pen.
Ref: B Knight (Kent).