In a highly entertaining match, McLeish, who relinquished his position as Scottish national manger last week, made three changes to the side who lost at home to Portsmouth last weekend.
Most significantly, 36-year-old Maik Taylor was recalled between the sticks.
The Northern Ireland keeper's heroics, particularly in the first half, won the game for the visitors as Birmingham went into the break not only with a clean sheet but also somehow in front, thanks to Gary McSheffrey's 24th minute penalty.
They had managed only one shot in the half - Daniel de Ridder's second minute shot which screwed well wide - compared with Tottenham's ten efforts, four of which were on target.
Taylor was first called into action in the tenth minute when centre-back Johan Djourou misguided a headed clearance.
The ball fell kindly for Dimitar Berbatov 12 yards from the goal, but the Bulgarian forward struck his shot straight at the grateful keeper.
It was all Spurs and after 20 minutes Berbatov's inside-out through ball found Darren Bent, whose swivelled shot from six yards was deflected agonisingly wide by Taylor.
The save of the match came after Birmingham had opened the scoring though McSheffrey's spot-kick.
In Birmingham's only attack in the half, Younes Kaboul, who missed Thursday's UEFA Cup game due to a groin injury, chopped down the former Coventry forward after his give-and-go with Larsson paid off.
He stepped up to the spot and cracked it straight as Paul Robinson dived to his left.
Ramos rang the changes at the break - replacing Bent with Jemain Defoe and Kaboul with Tom Huddlestone - and it paid dividends almost immediately.
After only five minutes, Spurs had equalised through Keane after Djourou had pulled back Berbatov in the box.
The Republic of Ireland striker then latched onto Huddlestone's lofted ball after Fabrice Muamba had failed to clear.
His finish, with the studs of his right boot, put Ramos' team ahead and the relief was tangible.
However, Keane was to turn from hero to villain after being shown a straight red card with 20 minutes remaining.
His late tackle on Djourou was deemed by referee Phil Dowd as dangerous.
Birmingham's Cameron Jerome had levelled the scores six minutes before Keane's ejection during a rare attack, but it was former Arsenal midfielder Larsson who will rightfully claim Monday's headlines with a superb winning strike.
His 30-yard stunner powered into the top right-hand corner beyond the groping hand of Robinson and lifted Birmingham two points above their north London hosts.