We develop adaptive self-interference cancellation algorithms for both filter-and-forward and decode-and-forward multiple-input multiple-output relays. The algorithms are blind in the sense that they only exploit the spectral properties of the transmitted signal to identify the self-interference channel, while dealing with frequency-selective channels and arbitrary signal spectra. Our approach is non-intrusive in the sense that the algorithms can successfully identify, track, and cancel the self-interference distortion while the relay is operating in its normal mode. We study the stationary points of the algorithms and analyze under which conditions they achieve perfect cancellation of the self-interference. Simulation results show that the algorithms provide residual self-interference levels below the noise floor by using the time samples of only a few OFDM symbols.