Final Edit (Hopefully)
I have resolved every issue presented here. It took a while to pull off, but I now have a working Android application. Thank you, Allegro! 
Perhaps you could post the main issues you ran into and how you resolved them for the benefit of others?
Perhaps you could post the main issues you ran into and how you resolved them for the benefit of others?
Good idea.
What I Did Incorrectly
The instructions to compile for Android is incredibly convoluted, or so I thought. I made quite a few idiotic mistakes, of which I'll try to list in detail here.
1. Missing the "android" Command: Despite installing the SDK and NDK, the android command was absent from my path. I solved this by using its absolute path which, in my case, happened to be $HOME/android-sdk/tools/android.
2. Missing the "ant" Command: I downloaded the JDK, but I didn't have this command. Running sudo apt-get install openjdk-7-jdk quickly resolved this issue.
3. Missing Android Build Tools: Somewhere along the line I was encountering errors whilst building a few files, which I resolved by looking at the Android SDK Manager (which can be accessed via the terminal by using the android command above). Look under the latest Android API (Android 4.3 API 18 in my case) and ensure that each package is properly installed. Doing this solved a few of my issues.
4. Wrong Allegro5.jar Location: I accidentally copied Allegro5.jar into the ./jni directory instead of ./libs.
5. Incorrect Android Targets: The README_android.txt file calls for Android 10, whereas the latest version is 18. Just make sure you use the latest version, or else you may encounter errors like I did.
6. Compiling Multiple Sources: This was a big one for me. I was finally able to compile a single .c file but wanted to do several .cpp ones. To do this, go into ./jni/Android.mk and edit "LOCAL_SRC_FILES" like so:
LOCAL_SRC_FILES := \
/path/to/file/a.cpp \
/path/to/file/b.cpp \
/path/to/file/c.cpp
Just include a new black-slash for each subsequent file (excluding the last one).
Final Notes
I encountered a few other, small issues, but those were quickly resolved by trial and error. Just keep at it and it'll work out eventually. 
5. Incorrect Android Targets: The README_android.txt file calls for Android 10, whereas the latest version is 18. Just make sure you use the latest version, or else you may encounter errors like I did.
You can also install older SDK versions using the sdk manager to "fix" that. If you want to make sure you're limiting yourself to a given sdk version for compatibility reasons, the least error prone way of doing so is by using the sdk for the specific version you want to stay compatible with.
Thanks. I was considering trying my hand at this as well and this may just come in handy. 
Thanks. I was considering trying my hand at this as well and this may just come in handy.
You should definitely give it a go. It's neat having a portable version of an application of your own design. Just be sure to read over the instructions carefully!