We present a $^{125}$Te nuclear magnetic resonance (NMR) study in the three-dimensional spin web lattice Cu$_3$TeO$_6$, which harbors topological magnons. The $^{125}$Te NMR spectra and the Knight shift $mathcal{K}$ as a function of temperature show a drastic change at $T_text{S}sim 40$ K much lower than the Neel ordering temperature $T_text{N}sim 61$ K, providing evidence for the first-order structural phase transition within the magnetically ordered state. Most remarkably, the temperature dependence of the spin-lattice relaxation rate $T_1^{-1}$ unravels spin-gap-like magnetic excitations, which sharply sets in at $T^*sim 75$ K, the temperature well above $T_text{N}$. The spin gap behavior may be understood by weakly dispersive optical magnon branches of high-energy spin excitations originating from the unique corner-sharing Cu hexagon spin-1/2 network with low coordination number.