Making different APKs is sometimes a good choice, to reduce the download size. Just think about it, hundreds of thousands of people will be downloading these extra megabytes from the Play Store with every update! There are some strategies for creating and maintaining such split APK's: it's important to keep the version numbers in proper order. See https://stackoverflow.com/a/20029256/192373 and the improvement by Ashwin S Ashok below.
Whether you choose to split the APK's, or keep a monolithic one, feel free to use my "patent": put your executables into libs/armeabi-v7a (or other subfolder, according to target ABI) , and give them names that all start with lib and end with .so (e.g. lib_vim_.so). This will turn on the installation magic, and the appropriate files will be unpacked (and updated) into your /data/package/lib folder with executable permissions.