Soft Bricked Nexus 4
USB Debugging is not relevant, it doesn't come into play here, but you must be able to connect it to your computer via USB.

The first thing you have to do is unlock the bootloader, luckily the Nexus 4 does not require anything special to unlock the bootloader. From the fasboot screen, on your computer use the command:

sudo fastboot oem unlock

And follow the instructions on the screen to confirm the unlock and wipe process. 

If this fixes it, your done... But to flash the latest firmware, you can go to: https://developers.google.com/android/nexus/images which has the images and instructions to flash the device from the bootloader (fastboot). It is literally as simple as downloading the appropriate image, expand the archive, and run ./flash-all.sh script

If you need adb and fastboot, they are available in the normal Ubuntu software repositories. 

Nexus devices are wonderfully simple to work with, and are virtually unbrickable.