It's rarely necessary to invert a matrix. Do you need to solve a linear system with this matrix? One option is to feed the matrix to a sparse factorization library to perform a LU (or Cholesky if your matrix is positive definite) decomposition and exploit sparsity. Another option is to write a relatively simple code to perform the usual Thomas tridiagonal factorization but use dense LAPACK routines to factorize the blocks. That would be relatively easy to do in Matlab, but it wouldn't bother to pivot other than inside the blocks.
If each matrix is Hermitian in the blocks then each matrix will have real eigen values and corresponding eigenvectors will be orthogonal. Use Hockney method to find solution. May see our papers on Poisson's equation.