Understanding the definition of signal's bandwidth
"tutor explained that the bandwidth indicates how fast the signal is changing"


This is not correct even in a hand-waving fashion.  As you were told, a pure sinusoid $x(t) = \sin(2\pi f_0t + \theta)$ has zero bandwidth (according to the definition of bandwidth that your tutor is using) but that does not mean that the sinusoidal is not changing at all! It is changing and its maximum slope (a.k.a. "how fast the signal changing") is 
$$\max \left| \frac{\mathrm dx}{\mathrm dt}\right| = \max \left|2\pi f_0 \cos(2\pi f_0t+\theta)\right| = 2\pi f_0.$$ More generally, a result due to Bernstein says that if the maximum frequency in a generic $x(t)$ bounded within $[-1,1]$ is $f_0$, that is, $X(f) = 0$ for $|f| &gt; f_0$, then 
$$\max \left| \frac{\mathrm dx}{\mathrm dt}\right| \leq 2\pi f_0.$$
In short, the minimum frequency (in a bandpass signal) is irrelevant; it is the maximum frequency that matters, and the "how fast the signal is changing" depends on the maximum frequency and not on the bandwidth.

Turning to the rectangular pulse that puzzles you, note that the signal doesn't have a derivative (as far as mathematicians, including Bernstein, are concerned) when the signal makes the abrupt transition from high to low or vice versa but here on dsp.SE we have no qualms about saying that the derivative is $\pm \infty$ at these points.  As MattL says in a comment, if you know the Fourier transform of a rectangular pulse (hint: $\text{rect}(t) \leftrightarrow \text{sinc}(f)$), then you know that the rectangular pulse has no maximum frequency (there is no finite $f_0$ such that $\text{sinc}(f) = 0$ for all $|f|&gt;f_0$) and that the infinitely fast changing of the rectangular pulse is well-supported by the infinite bandwidth of the rectangular pulse.