Check to see if there's a local cake supply store. If they don't have the spray that's already been mentioned, they might sell powder food color. I've used the Chefmaster brand black before and it gave decent results.**
I don't know how it tastes in large quantities, but if it's okay without being mixed, I'd be inclined to try to find some way to make the surface slightly tacky (maybe a mist of water?) and then dry brush it on. That way, you can work around any details that might already be on the cake. If you did fondant, you'd have to cut around the details (which would leave everything looking sunk in), or lift them all off and reset them.
The folks at the cake supply place might have other ideas of how to fix it. (and they'd know what they have to work with).
** I was dying cookie dough to make cookies that looked like a pie chart. It probably would've performed better in icing.