Is it ever possible for a Kohen Gadol to perform the Mitzvah of Yibum. After all, every case of Yibum involves a widow which the Kohen Gadol is not allowed to marry?
Indeed he can't perform yibbum - he would have to perform chalitzah instead. The reason is that while yibbum is a positive mitzvah, it's opposed by the positive mitzvah to marry a virgin (Lev. 21:13) and the negative mitzvah to not marry a widow (ibid. :14) - and a positive mitzvah can't override a positive plus a negative one.
Even if the original marriage was never consummated, there's still the problem of her being a widow. It is true that then the positive mitzvah of yibbum ought to override that - but this would only apply to the first time they have relations. Since the Sages were concerned that he might continue to cohabit with her afterwards too (and then he'd be violating the prohibition without performing any positive mitzvah), they banned him from performing yibbum at all.