Localized spins and itinerant electrons rarely coexist in geometrically-frustrated spinel lattices. We show that the spinel CoV2O4 stands at the crossover from insulating to itinerant behavior and exhibits a complex interplay between localized spins and itinerant electrons. In contrast to the expected paramagnetism, localized spins supported by enhanced exchange couplings are frustrated by the effects of delocalized electrons. This frustration produces a non-collinear spin state and may be responsible for macroscopic spin-glass behavior. Competing phases can be uncovered by external perturbations such as pressure or magnetic field, which enhance the frustration.