Suppose I cast a creature spell, let's say Elvish Mystic. It enters the stack, then in response another player casts Counterspell targeting it. Could I, in response to that, cast Avoid fate or is the Elvish Mystic not considered a permanent until the spell resolves and thus Avoid Fate has no effect?
It's not a permanent while it's on the stack.
110.1. A permanent is a card or token on the battlefield.
111.1. A spell is a card on the stack.
Before it resolves, it's a spell (on the stack). After it resolves, it's a permanent (on the battlefield).
So no, you cannot cast Avoid Fate targeting a Counterspell that's targeting your Elvish Mystic on the stack. (It's not that Avoid Fate has no effect; you can't cast it in the first place.)
No. A permanent is an object on the battlefield. If an object is on the stack, it's not on the battlefield. Only spells and abilities can be found on the stack. This particular spell would be called a "permanent spell", which means a spell that would become a permanent on resolution, but it's not a permanent. (This is the only case I can think of where something is said to be something of the form XXX YYY without being both XXX and YYY.)