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?

Hint: A promising strategy is to prove that the claim

If we remove two opposite-colored squares from a $2m\times 2m$ chessboard, we may tile the remaining part with $2\times 1$ dominoes.

by induction on $m$. The case $m=1$ is trivial. Assume that the claim holds for some $m\geq 1$ and consider a $(2m+2)\times (2m+2)$ chessboard. If both the removed squares do not lie on the boundary of the chessboard, there is nothing to prove. Hence we may assume that at least one of the removed squares lies on the boundary. And we may also start tiling by following a spiral, starting next to the removed square on the boundary:

Another interesting idea is just to place $31$ non-overlapping dominoes on a $8\times 8$ chessboard and start playing Sokoban with the placed dominoes, in order to free the wanted squares.
