Strictly speaking, it requires WiFi. But I guess you could use one iPhone as a hotspot and feed wifi to an iPhone and Apple Watch so you could update that way.
I wish they would get rid of this restriction. We get better speeds via LTE than over WiFi in the place we are at now.