How can I fix internal storage growing for no reason? Why does internal storage keep growing over the time for no reason? At some point it becomes simply impossible to update apps, due to lack of sufficient memory space. Not even cache cleanup can save it, and I have moved as many apps as I could to SD card with no help. 

Apps need to be uninstalled then installed again on every update. Depending on the app this is problematic since they have lots of custom settings, and I have never seen that automatic Google servers backup and restore working whenever I needed it. Fortunately for stock preloaded apps your settings are not lost, since you can just remove updates since stock version, not remove it.

This indicates one of the main causes of this problem at least: app updates are somehow incremental, and performing the above workaround will somehow save some space, with same result of app updated to latest version. So innocent everyday app updates are no reason for causing internal storage to fill up.

What workarounds can I do in order to overcome this problem, besides the obvious ones like removing stuff or buying a new phone? I think I heard about re-partitioning phone memory to make internal storage point to external SD card, but I wonder if it will make things too much slower, for example. Please, point me to good solutions, even if they require rooting.
Before you can fix the issue you have to identify the cause. We have a few answers that deal with tracking down storage usage. But usually they target the external storage/SD-card. Here we are dealing with the internal storage, which is usually protected from normal user access and hence it's good (if not required) to have root. But other then that, the tools mentioned in the question should give you a good idea of how your internal storage is used:


Izzy's Answer on "Something is secretly eating up my Acer Iconia A500 internal memory and I need help finding it"
What can I do to manage my phone's internal storage?