If the $A_{ij}$ are $m \times m$ diagonal blocks, then your matrix rearranges into
$m$ diagonal blocks, each $n \times n$, by the permutation of row and column indices
$1 + a + b m \mapsto 1 + b + a n$, $a= 0 \ldots m-1,\ b = 0 \ldots n-1$. So just invert each diagonal block and permute back. For example
$$ \left[ \begin {array}{cccccc} a_{{1,1}}&0&0&a_{{1,4}}&0&0\\ 0 &a_{{2,2}}&0&0&a_{{2,5}}&0\\ 0
&0&a_{{3,3}}&0&0&a_{{3,6}}\\a_{{4,1}}&0&0&a_{{4,4}}
&0&0\\ 0&a_{{5,2}}&0&0&a_{{5,5}}&0
\\ 0&0&a_{{6,3}}&0&0&a_{{6,6}}\end {array} \right]^{-1} = \left[ \begin {array}{cccccc} b_{{1,1}}&0&0&b_{{1,4}}&0&0\\ 0&b_{{2,2}}&0&0&b_{{2,5}}&0\\ 0
&0&b_{{3,3}}&0&0&b_{{3,6}}\\b_{{4,1}}&0&0&b_{{4,4}}
&0&0\\ 0&b_{{5,2}}&0&0&b_{{5,5}}&0
\\ 0&0&b_{{6,3}}&0&0&b_{{6,6}}\end {array} \right]$$
where $$\left[\matrix{b_{11} & b_{14}\cr b_{41} & b_{44}\cr}\right] =
\left[\matrix{a_{11} & a_{14}\cr a_{41} & a_{44}\cr}\right]^{-1},\
\left[\matrix{b_{22} & b_{25}\cr b_{52} & b_{55}\cr}\right] =
\left[\matrix{a_{22} & a_{25}\cr a_{52} & a_{55}\cr}\right]^{-1},\
\left[\matrix{b_{33} & b_{36}\cr b_{63} & b_{66}\cr}\right] =
\left[\matrix{a_{33} & a_{36}\cr a_{63} & a_{66}\cr}\right]^{-1}$$