Try disabling extras-testing and extras-devel repo's to see if that frees up some memory. If that doesn't work, flashing would be the solution.

I could be wrong, but I think your phone goes back to factory state if you flash the emmc as well; flashing the firmware leaves the settings untouched.