Simple rotation... impossible?
It looks from your video as if you are rotating on the Global (World) axes, where what you would like is a rotation of the cube about one of its own local axes. If you haven't reoriented the cube in Edit Mode since it was created, its local axes will still run from the cube's center through the centers of its faces.

In that case, as you have, you can just set the Transform Orientation (in the header at the bottom of the 3D View)  to 'Local'. Set the pvot point to the center of rotation you want ..(e.g. 'Individual Origin(s))

The primary, default, orientation for transformations is always Global. To reach the secondary orientation ( the one in the header ), you have to hit the constraint key(s) twice. So hitting RXX, RYY or RZZ  will let you rotate the cube around its local axes.

(If you rotate all or part of an object's mesh in Edit Mode, that's all you have rotated. The object's local axes remain where they were before the edit.)