[freakboy3742]

If you want a smaller target, VOC (http://pybee.org/voc) can generate a "Hello World" APK in about 1.6MB.

VOC is compiler that takes Python code, and output Java bytecode. This means you can use the Android native UI components, because your Python code becomes indistinguishable from code written in Java. Combine with Briefcase (http://pybee.org/briefcase), and you can get an Android app with one command; combine with Toga (http://pybee.org/toga), and you can get a cross platform app using native system components.

If you want to see this in action, here's a video: https://www.youtube.com/watch?v=RisCgSIWwLA

(Full disclosure - I'm the primary author of these tools)