There are eight ways in which a $4\times n$ tiling can begin, shown and named in the picture below. We'll count the number with each kind of beginning configuration and add the results up to get $f(n)$.
Types A through E are easy. Any $4\times (n-1)$ tiling can extend A to give a $4\times n$ tiling, and there are no other ways to get a "type A" $4\times n$ tiling. So there are $f(n-1)$ "type A" $4\times n$ tilings. Similarly, there are $f(n-2)$ type B $4\times n$ tilings, and $f(n-2)$ as well of each of the types C, D, and E. That's $f(n-1)+4f(n-2)$ so far.
Tilings with starting configurations F, G, and H are a little harder to count. First define some helpful notation.
Let $f_T(k)$ represent the number of $4\times k$ tilings of type T, where T is a set of starting configurations. That lets us say from what we have above that $$f(n)=f(n-1)+4f(n-2)+f_{\{F,G,H\}}(n)\textrm.$$ We just have to figure out $f_{\{F,G,H\}}(n)$ in terms of $f$.
Clearly $f_{\{F,G,H\}}(n)=f_{\{F\}}(n)+f_{\{G\}}(n)+f_{\{H\}}(n)$; we'll compute each term separately. Also take note of the fact that $f(k)=f_{\{A,B,C,D,E,F,G,H\}}(k)$.
Now on to the counting. We'll look at type F first.
A "type F" $4\times (n)$ tiling is always configuration F extended by a "type B" or "type F" $4\times (n-2)$ tiling that has its center left domino removed. So $f_F(n)$ is exactly the number of $4\times (n-2)$ "type B" or "type F" tilings, that is, $f_F(n)=f_{\{B,F\}}(n-2)$. (The type B and F tilings are exactly the ones that have a center left domino to remove.)
A "type G" tiling is G extended by a tiling of type A, C, or G, with the lower left domino removed, so $f_G(n)=f_{\{A,C,G\}}(n-2)$. (A, C, and G are the tiling types with a lower left domino.)
A "type H" tiling is H extended by a tiling of type A, D, or H, with the upper left domino removed. So $f_H(n)=f_{\{A,D,H\}}(n-2)$. (A, D, and H are the tiling with an upper left domino.)
Substituting these last three expressions into the previous displayed equation yields
$\begin{align*}
f(n)&=f(n-1)+4f(n-2)+f_{\{B,F\}}(n-2)+f_{\{A,D,H\}}(n-2)+f_{\{A,C,G\}}(n-2)\\
&=f(n-1)+4f(n-2)+f_{\{A,B,C,D,F,G,H\}}(n-2)+f_{\{A\}}(n-2)\\
&=f(n-1)+4f(n-2)+f(n-2)-f_{\{E\}}(n-2)+f_{\{A\}}(n-2)\\
&=f(n-1)+5f(n-2)+f_{\{A\}}(n-2)-f_{\{E\}}(n-2)
\end{align*}$
Fortunately, A and E are the simplest patterns, and we know from our initial calculations (which we did before adopting the subscript notation on $f$) that $f_{\{A\}}(n-2)= f(n-3)$ and $f_{\{E\}}(n-2)= f(n-4)$. These final calculations give the recurrence relation you asked about: $$f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)\textrm.$$
I'll let someone else suggest good references for learning these techniques and just say experience helps. The hundredth one is a lot quicker to figure out than the first one!
Assume without loss of generality that the two squares to be removed are in different rows. (Otherwise turn the board 90°).
First cover the board in horizontal dominoes, and connect the two squares by a zig-zag line like this:
which follows the rule that if the line goes through one end of a domino, it immediately connects to another end. (The requirement that the two squares have different colors ensure that this will be true of the end of the path if only we start out in the right direction for this to hold at the beginning). Now you can flip dominoes along the zig-zag line to produce a covering that avoids the two squares.
With a bit of (easy) special-casing for the same-row case, this strategy can be extended to any size board as long as one of the side lengths is even and the other is $\ge 2$.
Best Answer
Any $4\times 4$ Latin square gives a colouring by repeating across the board, starting from the top left corner. You just need a Latin square where the $(1,1)$ entry is different to the $(3,3)$ entry.
For example $$ \begin{array}{c} 1234\\2143\\3421\\4312 \end{array} $$
which gives: $$\small\begin{array}{|c|c|c|c|} \hline 1234&1234&1234&1 \\ 2143&2143&2143&2 \\ 3421&3421&3421&3 \\ 4312&4312&4312&4 \\ \hline 1234&1234&1234&1 \\ 2143&2143&2143&2 \\ 3421&34{\tiny\fbox{2}}1&3421&3 \\ 4312&4312&4312&4 \\ \hline 1234&1234&1234&1 \\ 2143&2143&2143&2 \\ 3421&3421&3421&3 \\ 4312&4312&4312&4 \\ \hline 1234&1234&1234&1\\ \hline \end{array} $$
Any $4\times 1$ (or $1\times 4)$ tetromino will cover one square of each colour, so a collection of tetrominos will cover the same number of squares of each colour. Thus they cannot cover all but the center square (boxed), as you have an extra $1$ (e.g. bottom right square of board) and one less $2$ (center square).