Is it possible to cover a $8 \times8$ board with $2 \times 1$ pieces? 
We have a $8\times 8$ board, colored with two colors like a typical
  chessboard. Now, we remove two squares of different colour. Is it
  possible to cover the new board with two-color pieces (i.e. domino
  pieces)?

I think we can, as after the removal of the two squares, we are left with $64-2=62$ squares with $31$ squares of each colour, and - since the domino piece covers two colours - we can cover the new board with domino pieces.
But how should one justify it mathematically?

Completing an approach suggested by Thomas Andrews, if we can show that on the complete chessboard any proper subset of the white squares have more black neighbors than it has members, then Hall's marriage theorem will apply to the chessboard with two squares erased.
Suppose therefore, that a proper subset of the white squares are given. Since the red and green lines in the following diagram connect all the white squares, there will be at least one red or green line that goes from a square in the subset to a square outside of it:

Assume without loss of generality that there is a red line joining a square in the subset to a square outside the subset. (Otherwise mirror everything around the white diagonal).
Now pair up each white square with the black neighbor it is connected to by a blue line in this diagram:

This gives one neighboring black square for each white square. However the white square with a diagonal-partner that is not selected is additionally neighbor to the non-selected square's black partner which is not otherwise used.
So, as desired, our set of white squares has more black neighbors in total than there are white squares in the set.
