Killie boss Jim Jefferies made one enforced change to the side which drew at St Mirren last weekend, with William Gibson in for Medhi Taouil.
Butcher had stressed the importance of an early goal and his side were first to threaten after just 20 seconds.
A combination of Richie Foran and Odhiambo presented Dougie Imrie with a glimpse of goal but he fired high and wide over Alan Combe's crossbar from 18 yards.
A flurry of snow did not hamper the home side as they continued to press for an opener, forcing a few early corners and testing the Kilmarnock defence.
Killie goalkeeper Combe had to be quick off his line after 18 minutes, as Lionel Djebi-Zadi picked out Odhiambo with a well-placed through ball.
At the other end, a deflected clearance gave the visitors their first chance, which was pounced on by January signing Kyle, but his header was an easy take for Ryan Esson in the Inverness goal.
Kilmarnock were forced into a substitution midway through the first half, with Jamie Hamill on for the injured James Fowler after 26 minutes.
The lively Imrie continued to cause Killie problems but again could not keep his effort down when played through by David Proctor, firing high and wide from the edge of the box having beaten off the attentions of Frazer Wright.
Another snow shower followed, prompting referee Iain Brines to call for the yellow ball and it was not long before it ended up in the back of the net.
Black picked out Mihadjuks, who jumped well in the six-yard box to beat Combe with a excellent header, his second goal of the season.
Inverness started the second half on the offensive and should have doubled their lead three minutes in through danger man Mihadjuks, who flashed his near-post header wide of Combe's left-hand post from Foran's corner.
Irishman Rooney was added to the action on the hour, replacing Odhiambo, and injected some life in the tiring Caley Thistle attack.
Black released Rooney through the middle but he could not get the better of Wright, fouling the defender in the process.
The afternoon got worse for Jefferies' side, who were reduced to 10 men after 70 minutes after Kyle's wicked swing of the elbow on Proctor, giving Brines no option but to hand the striker a straight red card.
Despite their numerical disadvantage, Kilmarnock went in search on an equaliser and Gavin Skelton forced a good save low down from Esson after shooting through a cluster of bodies in the 18-yard box.
But Caley Thistle upped their quest to kill the tie, with Imrie attempting a cheeky chip from the left-hand side which was too easy for Combe.
Substitute Iain Flannigan almost rescued a replay six minutes from time, nodding Skelton's corner goalward but the ball was hooked off the line by Proctor.
Foran could have grabbed his first goal in Inverness colours after a real mix-up in the Killie defence, with Hamill providing the former Motherwell man with a chance at the death but he blasted over from four yards.
The game ended as contest in stoppage-time, Rooney hammering home Ross Tokely's neat delivery.
Sandy's Match Pic's are HERE
