First, just to be sure about the answers to this particular problem: the eigenvalues of the $4\times 4$ matrix are
$$0,\quad U\quad {\rm and}\quad U/2\pm \sqrt{(U/2)^2+4t^2}$$
When expanded to the first nontrivial order, the last two eigenvalues are
$$ 0 - \frac{4t^2}U \quad {\rm and} \quad U+\frac{4t^2}U. $$
Note that the corrections to the energy arise at order $t^2$ so the first-order perturbation theory is not enough in this case.
Second, the problem that prevents us from choosing the right eigenstates by the simple method is - as you correctly notice - that the matrix $V$, i.e. the matrix multiplied by $t$, has a vanishing upper left $2\times 2$ block as well as the right lower $2\times 2$ block - both of these blocks vanish.
So $V$ doesn't lift the degeneracy "inside the degenerate subspaces" only. This is, of course, related to the fact that the first-order $O(t)$ corrections to the energy eigenvalues vanish.
The standard formula of perturbation theory for the second-order corrections to energy is
$$ E_n = E_n^{(0)} + t \langle n^{(0)} |V|n^{(0)}\rangle + t^2 \sum_{k\neq n}\frac{\left| \langle k^{(0)} |V| n^{(0)} \right|^2}{E_n^{(0)}-E_k^{(0)}} +O(t^3) $$
Now, the $t^2$ term should give us $\pm 4t^2/U$ if it works. And of course, it does as long as we choose the right superpositions as the zeroth-order eigenvectors.
In particular, let's just reveal the eigenvectors. The eigenvalue $U$ comes with the eigenvector $(1,-1,0,0)^T / \sqrt{2}$ and similarly the eigenvalue $0$ comes with the eigenvector $(0,0,1,-1)^T / \sqrt{2}$. The $U+4t^2/U$ comes from $(1,1,0,0)^T/\sqrt{2}$ and similarly $0-4t^2/U$ comes from $(0,0,1,1)^T/\sqrt{2}$. The transposition means that the vectors should be written in the conventional column form. I added the $1/\sqrt{2}$ factor to make all of them normalized - and they're orthogonal, too.
For each calculated state (and its second order correction to energy), there's just one nonzero term in the $\sum_{k\neq n}$ sum. It has the denominator - the energy difference - $U$ if we calculate $E_n$ near $U$ or $-U$ if we calculate $E_n$ near $0$. And it connects the states $(1,1,0,0)^T/\sqrt{2}$ with $(0,0,1,1)^T/\sqrt{2}$ or vice versa.
Note that the matrix element of the $V$ matrix with the two $((1,1),(1,1))$ off-diagonal blocks between the two states I mentioned at the end of the previous paragraph is $1/2$ (from the two $1/\sqrt{2}$ normalization factors) times $8$ (because there are eight nonzero entries $t$ in your matrix, or $1$ in mine, and each of them contributes the same one to the matrix element).
So the matrix element is simply $4$ and the perturbation theory gives you the right $\pm 4t^2/E$ correction to the energy, from a single term, with the proper sign.
Now, the only step I haven't quite justified was the right choice of the eigenvectors - such as $(1,1,0,0)^T / \sqrt{2}$. How could I have seen this was the right one? Well, in this case, it was the intuitively right choice. While the $2\times 2$ blocks on the diagonal preserved the degeneracy, the energy shift came from the $2\times 2$ off-block-diagonal blocks and those made it natural to use this basis.
More generally, if we're in a similar situation that the degeneracy isn't lifted by first-order corrections in $V$ in the subspaces, what we really have to diagonalize is $V (H_0-E_0)^{-1\prime} V$ where the prime indicates that one has to omit the (divergent) terms from the vanishing energy differences (of course, we need a sensible result). This is the operator whose expectation value de facto gives us the second-order energy correction.
In this particular case, this operator will have a block diagonal form, $U^{-1} {\rm diag} [ ((+1,+1),(+1,+1)), ((-1,-1),(-1,-1)) ]$, and by diagonalizing, you get the right initial eigenvectors to deal with. Once you have the right eigenvectors to start with, their perturbations are infinitesimal at each order of the perturbation theory and the standard formulae of perturbation theory work without any extra subtleties, as the example above showed.
Again, the only thing one has to be careful about are the right zeroth-order initial eigenvectors. In a more generic case, they're given as eigenvectors of $V$ because $V$ lifts the degeneracy in each subspace. If it doesn't lift the degeneracy, only higher-order terms do so. But the operator $V (H-E_0)^{-1\prime} V$ plays the same role as $V$, and by diagonalizing it, we get the right initial eigenvectors.