The normal force does not do any work because, as you said, it is not being applied over some distance. The energy/work comes from your muscles (from the chemical energy stored in you body), where the forces are applied over some distance. The normal force just gives something to push off from.
As a simpler model system, you can think of it like a mass attached to a vertical compressed spring that is then suddenly released off of the ground. Even though the spring is pushing on the ground, the spring force is what does work on the mass. The potential energy stored in the spring is partially converted into the kinetic energy of the mass.
I mentioned the system to be me, so internal forces (muscles) should not have any role in my increase in kinetic energy.
"Internal" and "external" are just labels we apply to forces depending on how we define the system. They do not impact any of the physics. A force can do work and change the kinetic energy of something regardless of the label we put on it. So, even if you say your muscles are part of the system, the muscles will still do work, and they are still responsible for giving you kinetic energy.