Vine struck with goals in the 12th, 43rd and 57th minutes to earn Colchester a place in the fifth round of the FA Cup for the first time since 1979.
Visiting Coventry responded with a first-half equaliser from Julian Joachim, but that was their only joy of an otherwise miserable evening for the Division One club.
The U's had taken the lead in the first match at Highfield Road and they were in the driving seat again when Vine swept them in front on 12 minutes.
The U's striker shrugged off the challenge of defender Richard Shaw before racing through and beating keeper Gavin Ward with a cool finish.
Joachim had bagged the equaliser at Highfield Road and he did the same again on 25 minutes in this fourth round replay.
Icelandic international Bjarni Gudjonsson, enjoying only his second start for City, burst into the penalty area and he cut the ball back for the awaiting Joachim to rifle into an empty net.
But otherwise, Colchester always looked the better team. Scott McGleish disappeared into the dressing room after 40 minutes to have treatment on a head injury and it was while he was off Vine struck with his second.
Joe Keith helped on a cross from Karl Duguid and Vine turned superbly to smash the ball into the roof of the net.
McGleish did not appear for the second half, due to his cut head, and his replacement Wayne Andrews had a hand in the all-important third goal.
Substitute Andrews was fouled by Shaw and Keith's curling shot from the ensuing free-kick was spilled by keeper Ward. The alert Vine was on hand to sweep home the rebound from point-blank range to complete his treble.
There was no way back for woeful Coventry and their miserable night was summed up when defender Calum Davenport was sent off for two bookable offences in the 87th minute.
Both of Davenport's yellow cards were for off-the-ball incidents.
Colchester's reward is a trip to another Division One club, Sheffield United, in the last sixteen on Sunday February 15.