Solution methods for perturbed semi-infinite linear systems of block-Toeplitz type