The Android java code is compiled into Dalvik byte code, which is quite readable. I wonder, is it possible in theory and in practice to write a decompilation software for Dalvik byte code?
It's not only possible but has been done already, and not just once. Here's three I know about, and there may be more.
Kivlad by Cody Brocious
DAD by Zost (Androguard project):
JEB by Nicolas Falliere (commercial)
I think it should be possible even with current Java decompilers, by patching their code. They have at least one big difference - while JVM is stack-based, Dalvik is register-based. This difference could be handled with not so much code. Second difference - bytecode format. So you need use code, which is able to disassemble Dalvik bytecode format.
Don't forget http://dexter.dexlabs.org/ - Dexter is a static android application analysis tool.
jadx has both CLI and GUI, and it's open source.
Another tool is Bytecode Viewer:
Bytecode Viewer is an Advanced Lightweight Java Bytecode Viewer, GUI Java Decompiler, GUI Bytecode Editor, GUI Smali, GUI Baksmali, GUI APK Editor, GUI Dex Editor, GUI APK Decompiler, GUI DEX Decompiler, GUI Procyon Java Decompiler, GUI Krakatau, GUI CFR Java Decompiler, GUI FernFlower Java Decompiler, GUI DEX2Jar, GUI Jar2DEX, GUI Jar-Jar, Hex Viewer, Code Searcher, Debugger and more. It's written completely in Java, and it's open sourced. It's currently being maintained and developed by Konloch.
In addition to the software listed by Igor, there are also tools like apktool that can be used to decompile code : it transforms dalvik bytecode to smali, a language specific to the dalvik virtual machine (see instructions/opcodes here for example).
You can also edit resources in the application, and build the application back (but it will break the original signature as you will have to re-sign it with your own key)