Question: From a mathematical point of view it seems to be clear what's the difference between momentum and $mv$ and kinetic energy $\frac{1}{2} m v^2$. Now my problem is the following: Suppose you want to explain someone without mentioning the formulas what's momentum and what's kinetic energy. How to do that such that it becomes clear what's the difference between those two quantities?

From physics I think one can list essentially the following differences:

1. momentum has a direction, kinetic energy not
2. momentum is conserved, kinetic energy not (but energy is)
3. momentum depends linear on velocity, kinetic energy depends quadratically on velocity

I think is is relatively easy to explain the first two points using everyday language, without referring to formulas.

However is there a good way to illustrate the 3. point?

Answer: 
As a qualitative understanding, here's an example:

If you shoot a bullet, the rifle recoils with the same momentum as the bullet, but the bullet has a lot more Kinetic energy. Aren't you glad your shoulder is being hit by the rifle stock, and not by the bullet?
Consider two equal size lumps of wet clay moving toward each other at the same speed. Things are moving. But the center of mass is not. After they smush into each other, the resultant lump is not moving. Two lumps move in almost the same direction. They tap each other, and and the resultant lump keeps going.

It seems we need two different ways of measuring motion to make sense of this. The motion of the parts is much the same, but the total is very different.

Momentum might be loosely defined as the quantify of motion. $\vec p=m\vec v$. If two objects move at the same speed, the more massive one has a bigger quantity of motion. Of two equal mass objects, the faster one has more motion.

Momentum is a vector. It has a direction and magnitude. The direction is the same as velocity. Momentum adds like a vector. Two momenta in opposite directions cancel. The total momentum of the two lumps in opposite directions is $0$. This idea is useful for expressing the total motion of a compound object.

Energy might loosely be defined as the ability to change things. Energy has many forms that can be converted into each other.

* Kinetic energy is energy of a moving object. A bullet can poke a hole in its target. $E = mgh$.
* Potential energy is energy that comes from forces acting on a object. Shoot a bullet straight up. As it rises, it slows to a stop, losing all its kinetic energy. Because of its height and because of gravity, it will fall, gaining back all that kinetic energy. For such a bullet, it can be shown that $E = mgh = \frac{1}{2}mv^2$.
* Chemical energy is stored in molecular bonds. In a bomb, a chemical reaction can create fragments that have a lot of kinetic energy, much like bullets.

Energy has a magnitude, but not a direction. For example, there is no direction in chemical energy.

There is an obvious direction to kinetic energy, but this is purposely not part of what kinetic energy is. Kinetic energy is a number.

Kinetic energy is good for measuring the motion of all the parts of a compound object. The kinetic energy of two lumps of clay is the same, whether they move toward each other or away. It is the sum of the energies of the parts. Two lumps of clay deform when they smush into each other. If they more in the same direction and just tap each other, they can still smush when they hit something else.