WRONG ANSWER BELOW
Clearly, there are $4! = 24$ ways in a $2\times 2$ rectangle.
Now add one column to the right, making it a $2 \times 3$ rectangle. We already colored the $2 \times 2$ square in the left of this $2 \times 3$ rectangle (in $24$ ways), but the remaining two boxes are not colored yet. This two new boxes can be colored in $2 \cdot 1 =2$ ways.
Therefore, a $2 \times 3$ rectangle can be colored in $24 \cdot 2 = 48$ ways.
Similarly, adding one more column to the right will give two extra boxes, and there will be $48 \cdot 2=96$ ways to color a $2 \times 4$ rectangle.
Finally, adding one more column to the right, we will have $96\cdot 2 = 192$ ways to color a $2 \times 5$ rectangle.
Now we start adding rows.
Observe that, after adding one row to a $2 \times 5$ rectangle, although we will have $5$ new uncolored boxes, when the uncolored box on the very left is colored, the color of the remaining boxes are determined.
Since the box on the very left can be colored in two colors, there are $192 \cdot 2 = 384$ ways to color a $3\times 5$ rectangle.
Finally, we add one more row, and there are $384 \cdot 2 = 768$ ways.
EDIT: Apparently, I cannot delete my answer if it is accepted. As the comments below suggested, there are some cases where this method fails to create a $4 \times 5$ rectangle.