Premier League - Birmingham move out of bottom three
The result sees Birmingham, who will not be too concerned that they have still not won at Goodison since 1957, rise to 17th place, out of the bottom three at the expense of West Ham who plunge back into the drop zone.
Everton, who could have gone eighth and to within a point of a Europa League spot with victory, climb one place to ninth.
Off the back of the weekend's win over Newcastle, Everton manager David Moyes made just one change to his side, bringing in Heitinga for injured skipper Phil Neville, but he was forced into making another after just seven minutes, when the influential Arteta pulled up clutching his hamstring. Should scans prove the muscle to be torn, the Spanish midfielder could face six or seven weeks on the sidelines.
Birmingham boss McLeish meanwhile made three changes to the side that lost to West Brom, Martin Jiranek returning to the centre of defence with Sebastian Larsson and youngster Jordon Mutch also handed starts.
It was the home side who warmed up quicker on a cold night on Merseyside, Jermaine Beckford bringing Ben Foster into action early on with a crisp strike from just outside the box before the keeper again had to be alert to keep out a Leon Osman effort.
Birmingham's opener came against the run of play, Beausejour finishing expertly with his head from a lovely floated ball into the box by Mutch, who was making just his second Premier League start.
It was the Chilean's second in two games for the Blues, but he was indebted to the service from Mutch, who was later booked in bizarre circumstances as referee Peter Walton could not find his yellow card and instead brandished an imaginary one.
The goal initially rocked Everton - and the home faithful, who were stunned into an eerie silence - but they soon recovered and continued to enjoy the lion's share of possession for the remainder of the opening period.
When the equaliser arrived, it was nothing less than they deserved. And what a goal it was, Heitinga opening his Everton account - and scoring his first goal for over two years - with an absolute peach of a finish, right into the top corner with a sidefooted effort after Beausejour's poor clearance from a corner reached him at the edge of the box.
Foster was again tested as time ran out in the first half when Seamus Coleman, Arteta's replacement, nipped in front of Stephen Carr at the back post to aim a header on target, but otherwise Birmingham's back line held firm.
After the break, it was more of the same as Everton dominated possession, but failed to seriously trouble the visitors' defence.
Louis Saha found himself through on goal after turning Roger Johnson on 65 minutes and Beckford's delightful first touch put him into a similar situation four minutes later, but on both occasions the strikers deliberated too long and the chances went begging.
Osman saw another effort tipped over the bar by Foster but it was a simple save for the former Manchester United man to make.
Everton launched a final charge as the full-time whistle approached, but Foster was not troubled again and the Carling Cup holders held on for what might prove to be a crucial point in their fight against relegation.