I was finally able to get this working - and if you know how to do it, it i actually quite easy.
Most importantly, "no space left on device" is just what it says (for some reason I thought it indicates that the device didn't mount properly). I had only 1.5 MB left in /system and even though the Google Maps files are much smaller, it's still a space issue. So I got rid of the Bluetooth files in /system/apps and that did the trick.
Using the terminal isn't needed either - root explorer can conveniently remount /system in write mode!
Only remaining issue I have is that WikiSherpa's map function doesn't work (it crashes even after installing Google maps).