The best way is using the principle of inclusion exclusion.
There are $24^n$ ways to color the board so no columns is monochrome; $3\times 3\times 3-3$ ways to color each column, except for the three ways where that column is monochrome.
From these, we must subtract the colorings where no column is monochrome, but some row is monochrome. There are three choices for which row is monochrome, three choices for its color, then $3\times 3-1=8$ ways to fill each column. Therefore, it seems like the answer is $24^n-3\times 3\times 8^n$.
However, colorings with two monochrome rows have been double subtracted. These must be added back in. There are $\binom32=3$ ways to choose to the two rows.
If the two rows are the same color, there are $3$ ways to choose the common color, and $2^n$ ways to fill in the rest of the board.
If the rows are different colors, there are $3\cdot 2$ ways to color them, then $3^n$ ways to color the last cell in each row.
We are currently at $24^n-3\times 3\times 8^n+\binom32\times\Big(3\times 2^n+ 3\times 2\times 3^n\Big)$. We must now consider colorings where all three rows are monochrome. These were triple subtracted in the first step, then added back in three times in the previous step, so these need to be subtracted out again. There are only $24$ such colorings. The final answer is therefore
$$
24^n-9\times 8^n+18\times 3^n+9\times 2^n-24
$$
Yes, this can always be done.
Lemma. This can be done when every vertical and horizontal line with points on it contains exactly $3$ points.
Proof. In this case, all three points on a line must receive different colors.
We can think of this problem as a graph theory problem. Consider the bipartite graph with vertices on one side corresponding to the horizontal lines, and vertices on the other side corresponding to the vertical lines. Put an edge between two vertices when the corresponding lines intersect.
This is a regular graph, since every vertex has three edges out of it. Every regular bipartite graph has a perfect matching (this can be proven using Hall's theorem, for example here): a set of edges covering each vertex exactly once. Back in the grid, this corresponds to a set of points such that every line (vertical or horizontal) contains exactly one of them.
Color this set of points red, and remove the corresponding edges from the graph. The remainder is still regular and bipartite (every vertex has two edges left coming out of it), so there is another perfect matching, giving us another set of points with this property.
Color this second set of points green, and the leftover points blue. Now every line has exactly one red, blue, and green point on it.
In general, we can reduce the problem for an arbitrary grid to an instance of the lemma above.
First of all, we can get rid of horizontal lines with more than $3$ points on them. If a line has $k>3$ points, split it up into $\lfloor \frac k3\rfloor$ lines with $3$ points on them, and maybe a leftover line with $1$ or $2$ points. To do this, move the points so that they still have their old $x$-coordinates (and therefore lie on their old vertical lines) but instead of all having the same $y$-coordinate, only share $y$-coordinates in groups of $3$ or less.
If we can color the new arrangement of points, we could color the old arrangement. On each line with $3$ points, each color is used once; if there is a leftover line of $1$ or $2$ points, no color repeats on it. So each color is used at least $\lfloor \frac k3\rfloor $ times, with $1$ or $2$ colors possibly used $\lfloor \frac k3\rfloor + 1$ times, which still satisfies the conditions.
Then do the same thing for the vertical lines.
Second, we can get rid of horizontal lines with $1$ or $2$ points on them. On every such line, add new points to get up to $3$, making sure not to reuse $x$-coordinates (so that every point added lies on a new vertical line). The condition on the resulting line is that all $3$ points must be different colors, so if we get rid of the new points, the old line still satisfies the coloring condition.
Then do the same thing for the vertical lines. Now all vertical lines have exactly $3$ points on them, but there are some horizontal lines with $1$ point on them (the rest have $3$).
The total number of points must be a multiple of $3$ now. So the number of horizontal lines with $1$ point on them is also a multiple of $3$. Group them up in threes, and for every three points $(x_1, y_1)$, $(x_2, y_2)$, $(x_3,y_3)$ we group together, add more points $(x_4,y_1)$, $(x_4,y_2)$, $(x_4,y_3)$ and $(x_5,y_1)$, $(x_5,y_2)$, $(x_5,y_3)$. This creates two new vertical lines with $3$ points on them, and fills the horizontal lines with $1$ point up to $3$.
Now we are in the case of the lemma, and so we can color the points in a way that satisfies the condition. Undo everything we've done (deleting points we added, and merging together lines we split up) and we get a coloring of the original grid.
Best Answer
Let $\mathrm{Even}(n)$ be the number of colorings of the $1\times n$ board in which the number of red and of green squares is each even. Let $\mathrm{Odd}(n)$ be the number of colorings of the $1\times n$ board in which the number of red and green squares is each odd.
For $n\geq 2$, color the initial $1\times (n-2)$ board any which way; there are $4^{n-2}$ ways of doing it. Now, if the number of red tiles and the number of green tiles are both even (which happens in $\mathrm{Even}(n-2)$ of the colorings), then we can complete the coloring by either coloring both remaining tiles green, both red, or each of them either blue or orange. This gives six different colorings with the same "base" coloring on the initial $1\times (n-2)$ board.
If the number of red tiles and the number of green tiles are both odd (which happens in $\mathrm{Odd}(n-2)$ of the colorings), then we must color the remaining two tiles one red and one green, in some order. That's two different colorings with the same "base" coloring.
If one of the number of red tiles and of green tiles is even and the other is odd (which occurs in $4^{n-2} - (\mathrm{Odd}(n-2)+\mathrm{Even}(n-2))$ of the colorings), then one of the two remaining tiles must be the deficient color, and the other tile can be either blue or orange. That gives 4 possible completions (select which tile is either blue or orange, select the color).
A similar computation holds for $\mathrm{Odd}(n)$, since we are trying to preserve parity.
So we have the recursion $$\begin{align*} \mathrm{Even}(n) &= 6\mathrm{Even}(n-2) + 2\mathrm{Odd}(n-2) + 4\bigl(4^{n-2}-\mathrm{Odd}(n-2)-\mathrm{Even}(n-2)\bigr)\\ &= 4^{n-1} + 2\mathrm{Even}(n-2) - 2\mathrm{Odd}(n-2)\\ &= 4^{n-1} + 2\Bigl(\mathrm{Even}(n-2) - \mathrm{Odd}(n-2)\Bigr).\\ \mathrm{Odd}(n) &= 6\mathrm{Odd}(n-2) + 2\mathrm{Even}(n-2) + 4\bigl(4^{n-2}-\mathrm{Odd}(n-2) - \mathrm{Even}(n-2)\bigr)\\ &= 4^{n-1} + 2\Bigl(\mathrm{Odd}(n-2) - \mathrm{Even}(n-2)\Bigr). \end{align*}$$
Thus, we have: $$\mathrm{Even}(n) - \mathrm{Odd}(n) = 4\Bigl(\mathrm{Even}(n-2)-\mathrm{Odd}(n-2)\Bigr).$$
We also have $\mathrm{Odd}(0) = 0$, $\mathrm{Even}(0)=1$; and $\mathrm{Odd}(1)=0$ and $\mathrm{Even}(1)=2$.
From this, it should be easy to get a formula for $\mathrm{Even}(k) - \mathrm{Odd}(k)$, and from there a formula for $\mathrm{Even}(n)$ for all $n\geq 1$.