You can install kali linux on linux deploy and run with android VNC
I am running with linux deploy it on my AT&T 3g.
Im pretty sure your problem is in your configuration on preferences. Generally the SD is formatted to FAT which has maximum image file size 4095 MB. So pretty much if you want kali tools then hypothetically you could reformat your SD or external to ext4. There is also a permissions problem because of the image location. Here's how I got around it for now, I just started altering this phone 2 days ago so I'll keep you updated if you want. I moved the environment location to a folder in SD and it has consistently held up to 6000MB which is plenty for the os, necessary additions and a few fun kali tools.
Here's my mini pictorial, it's only my second post so maybe this will help.
Just do the settings like mine, Wait forever while it installs then after it finishes hit reconfigure. It takes a couple of minutes to reconfigure then you press start and wait until it's finished loading, press your home button, open VNC, make sure your port is 5900 and default password is "change me"
Open up a terminal and type "sudo su" make a password, update and make sure you have fun.
When you're finished go back to linux deploy, press stop and then use the menu button to exit the app