Ignore list of "allowed oxidation states" for metal complexes. "allowed oxidation states" might be the most common, but definitely not the only ones the atom is allowed to be in. For example, for $\ce{Fe}$ all oxidation state from -2 to +6 are known, for $\ce{Mn}$ -3 and from -1 to +7 are known, for $\ce{Ir}$ it is -3 and from -1 to +8 with tentative +9 reported for gas-phase monocation.
In $\ce{[Co2(CO)8]}$, most people say the charge of $\ce{Co}$ is 0. How does it become $\ce{[Co(CO)4]-}$?
It is traditionally assumed that ligands do not change oxidation state of the central atom and all atoms in them have same oxidation state as in a free molecule. At the same time, the total sum of all oxidation states of the particle must be equal its charge. Assuming total charge of the particle $-1$ and neutral ligands, the charge by necessity means that oxidation state of $\ce{Co}$ in $\ce{[Co(CO)4]-}$ is -1.
This is not the only case, there are numerous carbonyl anions with negative charges, like $\ce{[Mn(CO)5]-}$, $\ce{[Fe(CO)4]^{2-}}$. Compounds with even higher formal negative oxidation state of the central metal atom were reported, with anions like $\ce{[Mn(CO)4]^{3-}}$ and $\ce{[Cr(CO)4]^{4-}}$.
It would be a gross misunderstanding to assume that extra charge is located on the metal atom. It is siphoned onto $\ce{CO}$ ligands via $\pi$-backbonding. However, again, metal-ligand interactions are traditionally ingnored in calculation of oxidation state.
Truly negatively charged metal atoms are much rarer, but still happen. Example would be salt $\ce{[Na(15-crown-5)]Na}$ with sodium anion. Such salts are extremely powerful reducers.