When I read about Euler angles I see that they rotate also the initial coordinate frame with the shape that is being rotated (https://www.youtube.com/watch?v=q0jgqeS_ACM). Why this is so? Why we don't rotate around some fixed coordinate system? In this case the gimbal lock will not occur either, right?
This is just a convention. It is done because it gives more of a local representation. That is to say if you are in a plane, your pitch is local and independent of yaw. If you used fixed axes, your pitch would be dependent on your yaw and roll.
You can also define a orientation by three rotations about fixed axes. You will still run into gimbal lock either way. It can be shown that any three parameter representation of rotations will result in at least two singularities. That is why quaternions are so popular, because they have four parameters they do not have the same problem.
In the case of rotations, since they are not vectors, we cannot impose normal vector space ideas on them like orthogonality or linear independence. This is why Euler Angles can become gimbal locked. For example consider the typical Yaw, Pitch, Roll sequence of rotations. In that case there is a sequence of rotations which will attain any given orientation and at any given orientation we can instantaneously rotate in any orientation by changing the values of the angles. In other words there is a full rank relationship between differential movements in the Euler angles and my desired change in orientation. This is true for all points of orientation except when pitch is 90 degrees. In that case, yaw and roll become the same degree of freedom. I highly recommend that you try this with an object. Try the sequence Yaw 90, Pitch 90, Roll 0 and then try Yaw 0, Pitch 90, Roll 90. You should have the same end result. Now try Yaw 45, Pitch 90, Roll 45. You will again have the same result. This is what we call gimbal lock. Why the term "lock"? Because in that configuration you cannot infinitesimally move in a local yaw direction by infinitesimally changing one of the Euler angles. That is because we lost a degree of freedom at Pitch =90 degees (i.e. Yaw and roll move the object in the same way) so there is one direction which can no longer be moved because two parameters move the system in the same direction.
To help you understand, it can be shown that rotations directly correspond to three parameters need to describe the position on a circle and a sphere. The technical term is that the 3D rotation group is isomorphic to $S^1\times S^2$ where $S^1$ is the circle and $S^2$ is the sphere. For a sphere, we parameterize it with spherical coordinates such that $r=1$, namely we use latitude and longitude. Now consider what happens if we set our longitude to 0 degrees and move to the north pole. Our latitude continually increses from 0 to 90. When we get to the north pole, our longitude is 0 but suddenly, it doesn't matter what our longitude is. All longitudes are the same point at the north pole. Now this the is key point, our longitude still must have a particular value, say it is 0. Now say that we want to move one milimeter down the 90 degree meridian, we cannot do it unless our longitude value jumps to 90. In other words we cannot move infinitesimally in any direction expect along the 0 meridian without our longitude jumping to a new value, we have lost a degree of freedom. This is precisely what is happening in the gimbal lock circumstance.