HTC One M7 - Unauthorized in adb

It looks like you know how this works, but for anyone who may not, normally /data/misc/adb/adb_key contains the public keys of all the computers that have adb access to your device, which on your computer is located somewhere like ~/.android/adbkey.pub. If you did have root, you could just use su from the Terminal app, then create the file (say by copying or appending the adbkey.pub file from the /sdcard/ to /data/misc/adb/adb_key).

Without root, it's more challenging. As you note, the way it's supposed to happen is that connecting a device that's never been seen before will result in you being prompted to accept the key from the RSA dialog on the device. But if THAT'S not happening, I suspect that something is wrong with the ADB connection itself. Are you able to verify that adb is working with another device? The command adb devices issued from your computer can tell if your computer sees the device. On Linux devices lsusb will also show whether the device is recognized as connected to usb. Is your computer able to recognize other devices? You say that you've tried re-running adb-- for anyone who may be reading this, doing an adb kill-server followed by an adb start-server is one way to do this.

If you don't want to root your device, you may consider installing a custom recovery instead such as TWRP2, which will allow you to boot into recovery mode as root temporarily to make the change without having to actually touch the /system partition directly. When you're done putting your key into place, you can always re-flash the original recovery and should be good-as-new. Looks like on the HTC One you can use fastboot to flash to the correct partition via the command: fastboot flash recovery recoveryfilename.img. Fastboot is part of the SDK, and it's in the /platform-tools directory. You may need to run it with root privileges.