I think this coloring works. Color each row 0 1 2 0 1 2 0 (so the 1st column is all 0, the 2nd is all 1, etc.). This gives you 21 zeros, 14 ones, 14 twos. A straight tile covers three the same (if it's vertical) or one of each (if it's horizontal). If we say it covers $a$ zeros, $b$ ones, and $c$ twos, then in either case $a\equiv b\equiv c$, modulo 3. It follows that the four spaces left after you place the 15 straight tiles are 4 0 0 (that is, 4 zeros, no ones, no twos), or 2 1 1 or 0 2 2. Now the L has to cover some permutation of 2 1 0, and the uncovered square has to be some permutation of 1 0 0. Some of these work, e.g., 2 1 0 plus 0 0 1 gives 2 1 1. But there is no way to add 1 0 0 to any permutation of 2 1 0 to get any of 4 0 0, 2 1 1, or 0 2 2, so the uncovered square can't be a zero, that is, it can't be in the 1st, 4th, or 7th column.
Applying the transpose, it can't be in the 1st, 4th, or 7th row, either. That leaves only 12 places where it can be. By symmetries of the square, these 12 places are of only three types, so if you can find a tiling leaving each of these three types uncovered, you're done. Ross has found a tiling leaving what I'd call $(2,2)$ uncovered; now it remains to do $(2,3)$ and $(3,3)$.
Suppose you have a tiling of length $n+2$. This can be built from:
- a tiling of length $n+1$ followed by a single tile; OR
- a tiling of length $n$ followed by a double tile
Let $T_n$ be the number of different ways of tiling a $1\times n$ space. Then for $n\ge1$
$$T_{n+2}=T_{n+1}T_1+T_n=3T_{n+1}+T_n \tag{1}$$
and for the "base" cases: $T_1=3,\:T_2=10$. Then by (1)
$$\begin{array}{l}
T_3=33 \\
T_4=109 \\
T_5=360 \\
T_6=1189
\end{array}$$
So the hallway must be at least six units long for 1000+ different tiling possibilities.
The recursion is Fibonacci-like and can be written in matrix form as:
$$\begin{bmatrix}T_{n+2}\\T_{n+1}\end{bmatrix}=\begin{bmatrix}3 & 1\\1 & 0\end{bmatrix}\begin{bmatrix}T_{n+1}\\T_{n}\end{bmatrix}$$
from which the characteristic equation is $(3-\lambda)(-\lambda)-1\times1=0 \implies \lambda^2-3\lambda-1=0$ which has solutions $\lambda=\frac{3\pm\sqrt{13}}{2}$
So we seek a formula for $T_n$ of the form $T_n=a\left(\frac{3+\sqrt{13}}{2}\right)^n+b\left(\frac{3-\sqrt{13}}{2}\right)^n$. Substituting for some values of $T_n$, e.g. $T_3,T_4$ to be safe, you can solve to get
$$T_n=\frac{1}{\sqrt{13}}\left\{\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{13}}{2}\right)^{n+1}\right\}$$
It turns out that this formula works for $n=1,2$ as well even though the recursion didn't cover these cases. The formula can be proven by induction.
Appendix - Obtaining a Closed-Form Solution
In the formula $T_n=a\left(\frac{3+\sqrt{13}}{2}\right)^n+b\left(\frac{3-\sqrt{13}}{2}\right)^n$ let $a=a_1+a_2\sqrt{13},\:b=b_1+b_2\sqrt{13}$ (with $a_1,a_2,b_1,b_2$ all rational numbers). Then from $T_1=3,T_2=10$ we get:
$$\begin{align}
T_1&=(a_1+a_2\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^1+(b_1+b_2\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^1&=3 \\
T_2&=(a_1+a_2\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^2+(b_1+b_2\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^2&=10
\end{align}$$
and from this (by equating rational multiples of $1,\sqrt{13}$) we obtain four simultaneous equations:
$$\begin{array}{rccccccccc}
T_1[1]: & 3a_1 &+ &13a_2 &+ &3b_1 &- &13b_2 &= &6 \\
T_1[\sqrt{13}]: & a_1 &+ &3a_2 &- &b_1 &+ &3b_2 &= &0 \\
T_2[1]: & 11a_1 &+ &39a_2 &+ &11b_1 &- &39b_2 &= &20 \\
T_1[\sqrt{13}]: & 3a_1 &+ &11a_2 &- &3b_1 &+ &11b_2 &= &0 \\
\end{array}$$
with solution $a_1=b_1=\frac{1}{2},\:a_2=\frac{3}{26},b_2=-\frac{3}{26}$. So with a little manipulation
$$\begin{align}
T_n&=\tfrac{1}{2}(1+\tfrac{3}{13}\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^n + \tfrac{1}{2}(1-\tfrac{3}{13}\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^n \\[2ex]
&=\frac{1}{\sqrt{13}}\left(\frac{\sqrt{13}+3}{2}\right)\left(\frac{3+\sqrt{13}}{2}\right)^n + \frac{1}{\sqrt{13}}\left(\frac{\sqrt{13}-3}{2}\right)\left(\frac{3-\sqrt{13}}{2}\right)^n \\[2ex]
&=\frac{1}{\sqrt{13}}\left\{\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{13}}{2}\right)^{n+1}\right\}
\end{align}$$
Best Answer
The variant can be settled by splitting up into three cases:
We have $$ f_1(n) = f_1(n-1) + f_2(n-1) + 2 g(n-1) $$ because the last tile of a rectangle ending in a flat line can either be an I tile or an L tile oriented in two ways. We just have $$ f_2(n) = f_1(n-2) $$ since the only way to create an $f_2$-type rectangle is to put down two horizontal dominoes at the end, and just as before, we have $$ g(n) = f_1(n-2) + f_2(n-2) + g(n-1). $$
From here, it's also possible to write down a linear recurrence for just the total $f(n) = f_1(n) + f_2(n)$ in terms of $f(n-1), f(n-2), \dots$. We have $f(n) = f_1(n) + f_2(n) = f_1(n) + f_1(n-2)$, so it's enough to solve for $f_1(n)$. In fact, as a linear combination of $f_1$ and its translate, $f$ will satisfy the same recurrence relation as $f_1$ with different initial conditions.
From $g(n) = f_1(n-2) + f_1(n-4) + g(n-1)$, we get the infinite series $g(n) = f_1(n-2) + f_1(n-3) + 2f_1(n-4) + 2f_1(n-5) + \dotsb$, and this gives us a recurrence \begin{align} f_1(n) &= f_1(n-1) + f_2(n-1) + 2g(n-1) \\ &= f_1(n-1) + f_1(n-3) + 2g(n-1) \\ &= f_1(n-1) + 3f_1(n-3) + 2f_1(n-4) + 4f_1(n-5) + 4f_1(n-6) + \dotsb \\ \end{align} Subtracting $f_1(n-1)$ from $f_1(n)$, we get $$ f_1(n) - f_1(n-1) = \color{red}{(f_1(n-1) + 3f_1(n-3) + 2f_1(n-4) + 4f_1(n-5) + 4f_1(n-6) + \dotsb )} - \color{blue}{(f_1(n-2) + 3f_1(n-4) + 2f_1(n-5) + 4f_1(n-6) + 4f_1(n-7) + \dotsb )} $$ and most of the red terms cancel with blue terms, leaving us with $$ f_1(n) - f_1(n-1) = f_1(n-1) - f_1(n-2) + 3f_1(n-3) - f_1(n-4) + 2f_1(n-5) $$ or $f_1(n) = 2f_1(n-1) - f_1(n-2) + 3f_1(n-3) - f_1(n-4) + 2f_1(n-5)$. As observed earlier, this also means that the recurrence $$f(n) = 2f(n-1) - f(n-2) + 3f(n-3) - f(n-4) + 2f(n-5)$$ holds.
The first few nonzero terms of the sequence are $1, 1, 2, 5, 10, 22, 49, 105, 227, 494, 1071, \dots$, as computed by @PeterKagey in the comments and in the upcoming OEIS listing.