Is it possible restore or update your iphone if you only have tethered internet?
As you said, yes, you do need to have a connection to download and verify the install, not just the download. Its the computer doing the update that needs an internet connection - not really the phone. 

In your case, the phone is currently in the update, which is probably running a very 'light' iOS bootstrap while your computer does the update. OS features like tethering would not be running then (nor anything much really), and so your computer would not recognize it as a connection, and the iPhone can't really do the verification in its state at that point either. 

The only way you could really do the update with tethered internet is to have another iPhone that you are tethered to.