Install apktool first:
Get it from http://ibotpeaches.github.io/Apktool/
Download latest apktool from here.

cd ~/
mkdir apktool
wget https://raw.githubusercontent.com/iBotPeaches/Apktool/master/scripts/linux/apktool
wget https://bitbucket.org/iBotPeaches/apktool/downloads/apktool_2.1.1.jar
mv apktool_2.1.1.jar apktool.jar
chmod +x apktool*
sudo mv apktool* /usr/local/bin/

You’ve now installed apktool.

Create a temp directory for apktool, and get your apk file.
Get your apk file via adb/from the connected phone via a file manager:

adb shell
cp /data/app/com.poke.media.pokemon/base.apk /sdcard/
adb pull /sdcard/base.apk 

Now, decompile it:

apktool d base.apk

The directory base will contain the decompiled files.

After working on it and making the necessary modifications, you need to install it after recompiling it:
apktool b base
adb install ./base/dist/base.apk

There will be an error because you havent signed it yet.

$ adb install ./new/dist/base.apk
5527 KB/s (18972821 bytes in 3.352s)
	pkg: /data/local/tmp/base.apk
Failure [INSTALL_PARSE_FAILED_NO_CERTIFICATES]

Signing recompiled apk files:
You need either the signtool that comes with java development kit (jdk)
Install jdk:

sudo apt-get install openjdk-9-jdk

If it has failed dependencies, like it did when I installed it on Ubuntu 16.04, try:

sudo aptitude install openjdk-9-jdk

jarsigner and keytool reqiured for signing will be installed by java jdk to the PATH. So, just do:

keytool -genkey -v -keystore my-release-key.keystore -alias mykey1 -keyalg RSA -keysize 2048 -validity 10000

Enter keystore password:  
Re-enter new password: 
What is your first and last name?
  [Unknown]:  Joel
What is the name of your organizational unit?
  [Unknown]:  None
What is the name of your organization?
  [Unknown]:  Somewhere
What is the name of your City or Locality?
  [Unknown]:  Trivandrum
What is the name of your State or Province?
  [Unknown]:  Kerala
What is the two-letter country code for this unit?
  [Unknown]:  IN
Is CN=Joel, OU=None, O=Somewhere, L=Trivandrum, ST=Kerala, C=IN correct?
  [no]:  yes

Generating 2,048 bit RSA key pair and self-signed certificate (SHA256withRSA) with a validity of 10,000 days
	for: CN=Joel, OU=None, O=Somewhere, L=Trivandrum, ST=Kerala, C=IN
Enter key password for <alias_name>
	(RETURN if same as keystore password):  
[Storing my-release-key.keystore]

jarsigner -verbose -sigalg SHA1withRSA -digestalg SHA1 -keystore my-release-key.keystore ./new/dist/base.apk mykey1

Now install the apk:

adb install ./new/dist/base.apk
3863 KB/s (19077789 bytes in 4.821s)
	pkg: /data/local/tmp/base.apk
Success