No, it is not possible to remove the app from bootloader. ADB daemon is not running in the device in that tiny environment when the device is in fastboot mode and stock recovery doesn't offer shell access.
Your best bet is to flash a custom recovery, such as TWRP, CWM or Philz Touch from fastboot/download mode or from a tool using PC (if at all possible for an ordinary user) and boot straight into that recovery. Note that if the bootloader is not unlocked, unlocking a bootloader may (nowadays it does) cause a full wipe of user's data.
Once you're in a custom recovery environment, follow the instructions to remove the app:
- mount data partition at /data/, if not already mounted through GUI using volume buttons or touch as appropriate;
- determine package name of the troublesome app;
- Using shell or through a file manager feature of your recovery, go to /data/app/ or wherever the app is installed per /data/system/packages.xml or per this answer from Izzy
remove the apk or the app's directory (for Android 5.0 and above) containing the apk using the command:
adb shell rm -rf PATH
# PATH refers to location of APK under /data/ (excluding /data/media)
#Example:
adb shell rm -rf /data/app/com.android.chrome-1.apk
adb shell rm -rf /data/app-private/org.mozilla.firefox/
Optional: remove the data of the app from /data/data/ by removing the directory with name as package name of the app using
adb shell rm -rf /data/data/PACKAGE # PACKAGE refers to package name of the app
If the aforesaid instructions do not work out for you, make the Android boot into safe mode. My answer can help you out.
If you intend to backup contacts, make a backup of the directory /data/data/com.android.providers.contacts. The database inside it contains the contacts. To restore them after a factory reset, boot into a custom recovery and restore the backed up directory.
By the way, it does not matter whether you had USB debugging enabled in Android or not, once you've booted outside of Android OS.