Why does induction procedure of Euler characteristic fail for non-convex polyhedra? What am I missing? Euler characteristic of convex polyhedra is always $V-E+F=2$. 
Induction procedure reduces edges and vertices until we are down to one vertex whose $V-E+F=2$ and hence you are done.
The same induction procedure should also work for non-convex polyhedra and reduce to one vertex. So why does the induction procedure not work for non-convex polyhedra(giving $\neq 2$ values sometimes)? 
Please use elementary language in your description (for example, a talk to freshmen).

First, there is not just one induction proof of Euler's theorem. David Eppstein has gathered
20 distinct proofs at this link.

 
 
 
 
 


Second, most of the induction proofs do work for nonconvex polyhedra (but see below).
The one illustrated above (mentioned by @GrumpParsnip; figure from Eppstein's website) does not because it
uses stereographic projection. But if you instead just imagine topologically stretching
out one face boundary to become the outer boundary in the plane (rather than geometrically projecting),
the same proof works.

Third, as @Mariano Suárez-Alvarez hints, there are nonconvex polyhedra for which
the Euler characteristic is not $2$ (and for which some of the 20 proofs mentioned
above do not work). Only those polyhedra homeomorphic (stretchable) to
a sphere have $=2$ as the right-hand-side. If the "polyhedron" has a hole (like a torus)
or a cavity, the right-hand-side is $\neq 2$.
