Para instalar un custom recovery desde un linux tienes que abrir la terminal y poner estos comandos:

--Para instalar las herramientas necesarias (como indica OctavioHZG en su comment anterior):
sudo apt-get install android-tools-adb
sudo apt-get install android-tools-fastboot

--Para flashear el recovery (primero debes tener la depuración activada y poner el móvil en modo fastboot)
*fastboot flash recovery  recovery_image.img
*fastboot reboot

*Si no te deja usar los comando de fastboot prueba usándolos como super usuario (sudo).