Newcastle deservedly took Manuel Pellegrini's side to added time and probably had the better of things over 90 minutes, but they could not break the deadlock and instead left St James' Park digesting an unflattering defeat.
And while City's strike pair must take their share of the praise for neat finishes in the 99th and 115th minutes, Pantilimon also did everything that was asked of him.
City made 10 changes from the side that was beaten by Chelsea at the weekend, the least surprising of which involved the struggling Hart stepping down.
Natural rest and rotation meant the he was always likely to be excused duty but recent errors made the evening seem like an audition for his deputy.
A first-half save from Shola Ameobi, when partially unsighted, was good but a firm block when second favourite in a one-on-one with Papiss Cisse was even better.
Whether that proves sufficient evidence to drop England's number one is uncertain, but the Romanian keeper at least kept the question alive.
Newcastle showed five changes of their own, with the attacking fulcrum of Yohan Cabaye, Hatem Ben Arfa and Loic Remy all consigned to the bench.
The chosen XIs contested a scrappy 90 minutes, with neither doing enough to seal the win in regulation.
Both had chances to do so, though, not least a pair of close-range headers in the space of a minute at the death. Negredo saw his beaten clear by Tim Krul, but an unmarked Yoan Gouffran had no such excuse as he diverted Mathieu Debuchy's cross wide from well inside the six-yard box.
City's evening could have started embarrassingly, Joleon Lescott almost tripping on the ball as he carried it out of defence after just a minute.
Ameobi was lurking but Lescott was able to recover composure well enough to dribble past the striker and spare his blushes.
Newcastle had a more conventional attempt on goal in the ninth minute when Ameobi headed on for Cisse and the Senegalese striker prodded narrowly wide..
Moments later Stevan Jovetic was forced off injured, with Pellegrini summoning Negredo from the bench. With City starting lethargically the hosts went close again on the half hour, but Pantilimon made a good low save.
Moussa Sissoko started the move before working the ball left to Gouffran and getting on the end of the resulting cross.
His effort was blocked by Lescott but when Ameobi steered the rebound towards goal, City's back-up keeper got down well to palm wide.
A minute later Ameobi had the ball in the net but was ruled offside when he tapped home Cisse's shot across goal.
Had Cisse's attempt been better directed Newcastle would surely have led.
As it was the sides went in goalless, Vurnon Anita also going close for the hosts with a snap volley and Micah Richards ending the half with a strong run followed by a weak shot.
Pantilimon made a comfortable save early in the second half, Anita trying his luck from distance, and there were signs of life from City in attack as the previously anonymous Jesus Navas began to see more of the ball.
Navas created City's best chance in the 63rd minute when he came away with the ball following an ill-judged foray from Krul.
With the goal open Navas laid the ball back for James Milner, who curled wide of the far corner from a tough but manageable angle.
Both sides raided their bench in a bid to avert added time, David Silva, Cabaye and Ben Arfa bringing added flair but not the desired result.
With 12 minutes left in normal time Negredo made his first major contribution since his early introduction, waltzing into the box and floating in a delicate close-range chip that Krul flicked around the post.
Either side might still have won it in normal time, Negredo denied by Krul at close range and Gouffran nodding a glorious chance wide from even nearer.
Pantilimon made sure the shutout continued in extra-time when he came out to save well from Cisse, who had been put clear by Ben Arfa's smart ball.
That paved the way for the belated opener, a relatively simple affair that saw Dzeko drill a low cross into the Newcastle area, where Negredo applied the finishing touch.
The Spaniard first had to edge in front of Mapou Yanga-Mbiwa, who will be disappointed to have lost the battle with such ease.
The hard-working Dzeko got his own reward just before the break in extra-time by getting on the end of Milner's pass and successfully rounding the keeper.
Lescott cleared off the line when Ben Arfa's volley looked to have clawed one back for the hosts late on but it is City who will continue in the cup.