My internal storage has 400+ MB and the SD card has 9 GB left (I know SD card doesn't really matter). I deleted a lot of apps and I still get the message "Not enough space on your internal storage" when I try to download an app that is 7 MB.
This is not simple to solve. The solution that worked for me requires the device to be rooted, "Terminal Emulator" app and a file manager that can access to your whole file system (like "Root Browser"). I also have the "BusyBox" app installed which might be necessary to use the terminal emulator properly.
The first thing I did was to spot all files associated to the app I couldn't install. In my case, I achieved this in the terminal emulator with the commands
su find / -name "*[some part of the package name]*"
The first command is to gain root privileges in the terminal in order for the
find command to be able to search your whole file system. The second gives you a list of files and locations related to the app you want to install. The text in brackets
[ ] must be replaced by a part of the name of package which distinguishes from all others. In my case, the package is the FB Messenger. The APK file is called
com.facebook.orca-220.127.116.11.13.apk, so I decided to search this way:
find / -name "*orca*"
Then I deleted all the files and directories listed using the root browser (this is a brutal force method, may be it is not needed to delete them all...).
Finally, I rebooted my phone, let it start and installed the Messenger through Google Play Store. It worked :)
I hope this helps.