What does "ёшкин-кот" mean? And when do I use it?
It is an expletive that somebody says when something negative happens. It is not a vulgar phrase, and is somewhat of a euphemism.
This phrase can be literally translated as "A cat from Yoshkar-Ola" (in fact there is a monument to this cat in that city), but of course it is never used in this sense..
Most likely it is used as a euphemism, because a person already starts saying "Ё", which is a beginning of "ёб твою мать", but then is able to change what is being said. Thus it is akin to other similar phrases like "ё моё"(Yo of mine) or "ёлки палки"(spruce and sticks)/"ёлки зелёные"(green spruce).
Another similar word of this kind is "блин" that is used due to the first two sounds being soft Б and soft Л.
To use any of these you would need to find yourself in a negative situation... and you would say something like:
Ёшкин кот! Куда я засунул свои ключи?
Volodya provided you an accurate translation, and TT_ gave some additional background.
However, it's worth noting that "ёшкин-кот" (as well as "ёлки-палки", "ёлки-зелёные", "ёлки-моталки" etc.) is much different from euphemisms like "блин", "твою ж налево", "бляха-муха", and I would like to point out when you should not use "ёшкин-кот", and when you can hear it from native-speakers, as an answer to the "when do I use it?" part of your question.
- As most other euphemisms, do not use "ёшкин-кот" in any formal context. It is a casual phrase, and could be considered as an evidence of your immaturity and unprofessionalism when used inappropriately.
- "Ёшкин-кот", is used predominantly in a humorous context, where the joke is often the fact that you used this phrase. It is inherently humorous, whereas "блин" (euphemism of "блять"), "твою ж налево" (euphemism of "твою мать") or "бляха-муха" (same as "блин") are commonly used without humorous intentions. "Ёшкин-кот" is not likely to be heard as a strong emotional exclamation in a serious conversation. Especially it would be uncommon to hear it being stressed. To put it into context, if a person in a hospital receives news of a serious illness and exclaims loudly: "Ёшкин-кот!", people around might get confused, some might be even tempted to giggle, even when it would be inappropriate.
As @Askar Kalykov mentioned in a comment, it could be related to "Баба Яга". The following link seems to confirm this version:
I think, it should be rather "ежкин кот" (Ezhkin-kot) if it is a derivative from "Баба Яга". But "zh" of course could become "sh" at some point.
(Sorry I put it as an answer instead of a comment: 1. I can't comment due to lack of reputation; and 2. When I first saw this question, the first thing which came to my mind was "it must be ezhkin", and now after Askar Kalykov comment it looks plausible).
Most of the answers go beyond the scope of the question. The OP wanted to know what it meant and when to use it.
I'll start with part 2. You should probably never use it. It's a silly, archaic, and mostly regional expression and will not add to your proficiency in the language.
As to the meaning, the ё definitely puts the expression in the "almost profane" category, since it's using the first letter of a profane root. As to whether the origins are in Йошка-Ола or Баба-ёжка, no one will probably ever tell with confidence.