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?
Here is a good way to illustrate point 3:

Kinetic energy tells you how long of a *distance* you would need to apply a given force $F$ to an object to make it stop.

Momentum tells you how long of a *time* you would need to apply a given force $F$ to an object to make it stop.

Imagine you have a car moving at speed $v,$ and it brakes and comes to a stop after a distance *d* and time *t.* You now double the speed. It will take twice as long to stop, $2t$, so the momentum doubles. However, because it takes twice as long to stop, *and because it starts with double the speed,* it will go a distance of $4d.$ The kinetic energy has *quadrupled*.