How do we get energy to start walking? The answer seems obvious, it's our energy that gets converted into kinetic energy. But my question is how exactly? Which force is responsible for doing work on us so that we gain kinetic energy? It can't be friction as the point of contact with the ground is at rest. Is it some kind of internal force that does this work?
 A: Biomechanics is complicated!
The first thing we have to do is start falling.  We have to become out of balance, one way or another.  The easiest to visualize version of this is to consider starting to walk with our knees locked and our lower back locked.  This decreases how many degrees of freedom we have available to us and points to the one degree left: the ankles.  Dorsiflection muscles like Tibialis Anterior pull on tendons on the front side of the foot.  This decreases the net downward force that the front of the foot can cause (and thus increases the downward force on the heel), and the result is that you start to lean forward.
Wow, that was the hard part.  Once we start leaning forward, we can start using gravity to do the dirty work for us.  We let gravity pull our body down until we can start using our glutes to rotate the hip joint.  As long as we do this in concert with the effects of gravity (and we're pretty good after it with about 4+ years of practice), the result is that the downward portion of the forces generated by those glutes opposes gravity, keeping us from going further downward, and the lateral portion of the forces start to drive us forward.
And, of course, the forces driving us forward eventually work their way down from the hip muscles down to the bottom of the foot, where friction holds the foot in place.  As such, since the foot cannot move, the muscles and tendons pull the body forward.  If you think in force terms from the perspective of the foot and the muscles and tendons connected to it, the muscles contact, pulling on the tendons, and the tendons exert a forward acceleration on the body above it, accelerating it forward.
Now what makes walking take a few years to master is that one basically has to maintain this state as a series of falls.  If one falls a bit too far forward, one adjusts placement and timing so that the next step does not cause as much forward acceleration, and lets the torque of gravity on the body slow that acceleration down (when our weight is on the front foot, our center of mass is behind our foot, so the net effect of gravity pulling us down plus the forces applied to the ground with our feet push us backwards).
But all of this starts with a really strange move where we have to lose balance so that we can fall into the first step.  There are ways to move that don't rely on falling.  Many martial arts practice them.  However, they are very unusual feeling and not nearly as fast.  Most everybody falls a little because its more energy efficient.
A: In a battery operated toy the internal chemical energy stored in the battery is released and converted into internal forces through motors, gears etc. which cause the toy to move. In a similar way, our bodies release internal chemical energy which our muscles convert into internal forces which then move parts of our body. With practice we learn to move the right parts of our body in the right way so that we can walk, run, jump, swim etc.
In very simple terms (leaving out many, many details) the equivalent of a battery in our cells is a complex chemical called ATP. The breakdown of ATP in cells releases energy, and stores of ATP are built up again in a process that consumes glucose. Stores of glucose in our bodes are in turn replenished when we digest food.
A: You write

It can't be friction as the point of contact with the ground is at rest

However, you have to be careful that you're consistent about the difference between your system and its surroundings. The point of contact doesn't move, but the center of mass does.
Consider a person who falls vertically to the ground and lands on their feet without bouncing. Their only interaction with the ground is the normal force, whose point of contact is also fixed. But the normal force must do the work of arresting the fall, because there isn't any other interaction between the falling person and their surroundings.  The solution is that the center of mass moves over a finite distance while the normal force is doing work.  The same argument applies to your example of friction.
A: 
Is it some kind of internal force that does this work?

Yes.  If the body were a point mass, it wouldn't work (the ground isn't supplying the energy).  But the body is an extended mass, so it can accelerate different parts at different times by doing work on the moving parts.
In the first phase your leg muscles create a force between the ground and your upper body.  Since your upper body has the lower mass, it accelerates more than the ground.  Most of the KE of the interaction then goes into accelerating the body.
Then after the body is moving, the leg muscles switch and create a contractive force.  As the feet are (hopefully) not connected to the floor, this force is mainly between the upper body and the feet.  Since the feet are the less massive part, they are accelerated upward and forward to prepare for the next step.
