Nice FE! We claim that the answer is all triples of the form $(a, ak, ak\ell)$ for $a, k, \ell \in \mathbb{N}.$ Before proceeding with the problem, we label the unit cubes with $\mathbb{Z}^3$ in the standard way. Now, we will begin by showing that these triples do indeed work. Consider some triple $(a, ak, ak\ell)$ for $a, k \in \mathbb{N}.$ Firstly, it suffices to show that $(1, k, k \ell)$ works, since if we had a coloring function $C: \mathbb{Z}^3 \rightarrow \{0, 1, \cdots, kl-1\},$ then we could construct a function $C': \mathbb{Z}^3 \rightarrow \{0, 1, \cdots, a-1\}^3 \times \{0, 1, \cdots, kl-1\}$ as follows. Let $C'(x, y, z) = (x \% a, y \% a, z \% a, C(\left \lfloor \frac{x}{a} \right \rfloor,\left \lfloor \frac{y}{a} \right \rfloor,\left \lfloor \frac{z}{a} \right \rfloor)).$ Hence, it suffices to show that $(1, k, k \ell)$ works. In other words, we want to show that $(1, m, n)$ works when $m | n.$ Let's begin by solving the case $(1, m, n)$ in just two dimensions. Simply color some $m \times n$ rectangle with $mn$ different colors, and then dictate the conditions that $(x, y)$ is colored the same way as $(x+m, y+m), (x, y+n),$ and $(x+n, y).$ It's easily verified that these conditions uniquely determine the coloring of the $xy-$plane, and that any $1 \times m \times n$ rectangle on the $xy-$plane has all distinct colors. Now, we will color the point $(x, y, 1)$ the same color as $(x-1, y-1, 0),$ the point $(x, y, 2)$ the same color as $(x-2, y-2, 0)$, etc. until we color $(x, y, m-1)$ the same color as $(x-(m-1), y-(m-1), 0).$ Finally, we enforce the condition that $(x, y, z)$ is the same color as $(x-m, y, z-m)$ for all $x, y, z \in \mathbb{Z}^3.$ It's easily verified that this uniquely determines the color of all points in $\mathbb{Z}^3$, and that this coloring indeed works. We will now show that no other triples $(a, b, c)$ work. Let $C_{x, y, z}$ denote the color assigned to the point $(x, y, z)$ and let $S_{x, y, z}$ denote the multiset of colors assigned to the set of points $\{x, x+1, \cdots, x+a-1\} \times \{y, y+1, \cdots, y+a-1\} \times \{z, z+1, \cdots, z+a-1\}.$ Then, by looking at the multiset $S_{x, y, z} - S_{x+1, y, z} - S_{x, y+1, z} - S_{x, y, z+1} + S_{x+1, y+1, z} + S_{x+1, y, z+1} + S_{x, y+1, z+1} - S_{x+1, y+1, z+1},$ we have that $$\{C_{x, y, z}, C_{x+a, y+b, z}, C_{x+a, y, z+c}, C_{x, y+b, z+c} \} = \{C_{x+a, y, z}, C_{x, y+b, z}, C_{x, y, z+c}, C_{x+a, y+b, z+c}\}. \qquad (1)$$We will use $(1)$ to resolve the case where $a < b < c.$ Consider some $(a, b, c) \in \mathbb{N}^3$ with $a < b < c.$ From $(1)$ we have that for all $(x, y, z) \in \mathbb{Z}^3$, $$C_{x, y, z} \in \{C_{x+a, y, z}, C_{x, y+b, z}, C_{x, y, z+c}, C_{x+a, y+b, z+c}\}.$$As $a, b < c$, however, there exists an $a \times b \times c$ which contains both $C_{x, y, z}$ and $C_{x, y+b, z}.$ Hence, $C_{x, y, z} \neq C_{x, y+b, z}.$ Similarly, $C_{x, y, z} \neq C_{x+a, y, z}.$ Therefore, we can conclude that $$C_{x, y, z} \in \{ C_{x, y, z+c}, C_{x+a, y+b, z+c}\}.$$Suppose for contradiction that $C_{x, y, z} \neq C_{x, y, z+c}.$ Then, we have that $C_{x, y, z} = C_{x+a, y+b, z+c}$ by the above. By a symmetric result, however, we also have that $C_{x, y, z} = C_{x+b, y+a, z+c},$ so this implies that $C_{x+b, y+a, z+c} = C_{x+a, y+b, z+c}.$ However, there exists an $a \times b \times c$ which contains both $(x+b, y+a, z+c)$ and $(x+a, y+b, z+c)$, contradiction. Hence, our initial assumption that $C_{x, y, z} \neq C_{x, y, z+c}$ was incorrect, and we have that $$C_{x, y, z} = C_{x, y, z+c}, \forall x, y, z \in \mathbb{Z}^3. \qquad (2)$$With two symmetric results, we actually have the even stronger $$C_{x, y, z} = C_{x, y, z+c} = C_{x, y+c, z} = C_{x+c, y, z} \forall x, y, z \in \mathbb{Z}^3. \qquad (2)'$$Now, let's define the multiset $T_{x, y, z}$ as $\{C_{x, y, z}, C_{x, y, z+1}, \cdots, C_{x, y, z+c-1}\}.$ Call $T_{x, y, z}$ the "$(x, y, z)-$stick." By $S_{x, y, z} - S_{x+1, y, z} - S_{x, y+1, z} + S_{x+1, y+1, z}$ we have $$T_{x, y, z} + T_{x+a, y+b, z} = T_{x, y+b, z} + T_{x+a, y, z} \forall x, y, z \in \mathbb{Z}^3. \qquad (3)$$Hence, as there is a $a \times b \times c$ which contains both the $(x, y, z)$-stick and the $(x+a, y, z)$-stick, we have that $T_{x, y, z}$ and $T_{x+a, y, z}$ are disjoint. Similarly, so are $T_{x+a, y+b, z}$ and $T_{x, y+b, z}.$ Therefore, we have from $(3)$ that $$T_{x, y, z} = T_{x, y+b, z} \forall x, y, z \in \mathbb{Z}^3. \qquad (4)$$With $(2)', (3)$ we then have that $T_{x, y, z} = T_{x, y+\alpha b + \beta c, z}$ for any $\alpha, \beta \in \mathbb{Z}$, and so hence $T_{x, y, z} = T_{x, y+ \gcd(b, c), z}.$ If $b \nmid c$, then since $\gcd(b, c) < b$ there is an $a \times b \times c$ which contains both of these sticks, contradiction, and so hence we must have that $b | c.$ Let $P_{x, y, z}$ denote the union of the $(x, y, z)-, (x, y+1, z)-, \cdots, (x, y+b-1, z)-$sticks, for any $x, y, z \in \mathbb{Z}^3.$ We have by $S_{x, y, z} - S_{x+1, y, z}$ that $P_{x, y, z} = P_{x+a, y, z}.$ We also have from a symmetric version of $(4)$ that $T_{x, y, z} = T_{x+b, y, z}$ for all $x, y, z \in \mathbb{Z}^3$, which gives us that $P_{x, y, z} = P_{x+b, y, z}.$ Hence, these two results imply that $P_{x, y, z} = P_{x+ \alpha a + \beta b, y, z}$ for any $\alpha, \beta \in \mathbb{Z}.$ Therefore, we have that $P_{x, y, z} = P_{x + \gcd(a, b), y, z}$. If $a \nmid b$, then since $\gcd(a, b) < a$ there exists an $a \times b \times c$ containing both $P_{x, y, z}$ and $P_{x+\gcd(a, b), y, z}$, which would give a contradiction. Therefore, we must have that $a | b$. Together with $b|c$, we've resolved the case where $a< b < c$, since we've shown that only the case where $a| b | c$ works. There are now three more cases which haven't been resolved. Case 1. $a = b < c$ For convenience, let's reorder $a, b, c$ so that $b = c < a$. This clearly doesn't affect anything. Now, let $S_{x, y, z}, T_{x, y, z}$ denote the same things as before. By $S_{x, y, z} - S_{x+1, y, z} - S_{x, y+1, z} + S_{x+1, y+1, z}$ we have that $$T_{x, y, z} + T_{x+a, y+c, z} = T_{x, y+c, z} + T_{x+a, y, z} \forall x, y, z \in \mathbb{Z}^3. \qquad (5)$$Since there exists a $c \times c \times a$ containing both $T_{x, y, z}$ and $T_{x, y+c, z}$ we have that $T_{x, y, z}$ and $T_{x, y+c, z}$ are disjoint. Similarly, so are $T_{x+a, y+c, z}$ and $T_{x+a, y, z}$ and so from $(5)$ we obtain that $$T_{x, y, z} = T_{x+a, y, z} \forall x, y, z \in \mathbb{Z}^3. \qquad (6).$$Now, let's define $P_{x, y, z}$ as the union of the $(x,y, z)-, (x, y+1, z)-, \cdots, (x, y+a-1, z)-$sticks. From $(6)$ we have that $P_{x, y, z} = P_{x+a, y, z}.$ As $P_{x, y, z} - P_{x+c, y, z}$ is the difference between two $c \times c \times a$'s, we have that $P_{x, y, z} = P_{x+c, y, z}$ as well. Hence, combining this with before gives us that $P_{x, y, z} = P_{x + \gcd(a, c), y, z} \forall x, y, z \in \mathbb{Z}^3.$ If $c \nmid a$ then since $\gcd(a, c) < c$ there exists a $c \times c \times a$ containing both $P_{x, y, z}$ and $P_{x + \gcd(a, c), y, z}$. This is clearly a contradiction, and so hence we have that $c| a$ as desired. Case 2. $a < b = c$ Let $S_{x, y, z}, T_{x, y, z}$ denote the same things as before. From $S_{x, y, z} - S_{x+1, y, z} - S_{x, y+1, z} + S_{x+1, y+1, z}$ we have that $$T_{x, y, z} + T_{x+a, y+c, z} = T_{x+a, y, z} + T_{x, y+c, z} \forall x, y, z \in \mathbb{Z}^3. \qquad (7)$$Since $T_{x, y, z}$ and $T_{x+a, y, z}$ can be covered by the same $a \times c \times c$, we have that $T_{x, y, z}$ and $T_{x+a, y, z}$ are disjoint. Similarly, so are $T_{x+a, y+c, z}$ and $T_{x, y+c, z}.$ Therefore, $(7)$ tells us that $$T_{x, y, z} = T_{x, y+c, z} \forall x, y, z \in \mathbb{Z}^3. \qquad (8)$$Now, define $P_{x, y, z}$ as the union of the $(x,y,z)-, (x+1, y, z)-, \cdots, (x+c-1, y, z)-$sticks. We have that $P_{x,y, z} = P_{x, y+c, z}$ from $(8)$. Also, we have that $P_{x, y, z} = P_{x, y+a, z}$ since $P_{x, y, z} - P_{x, y+a, z}$ is the different of two $c \times a \times c$'s. Therefore, we have that $P_{x, y, z} = P_{x, y + \gcd(a, c), z}.$ If $a \nmid c$, then since $\gcd(a, c) < a$ there exists a $c \times a \times c$ which contains both $P_{x, y, z}$ and $P_{x, y + \gcd(a, c), z}$. This is a contradiction, and so therefore we have that $a | c$ as desired. Case 3. $a = b = c$ This already satisfies the condition that $a | b | c$, so we're done already. As we've exhausted all cases and shown that the condition of the problem can only hold when $a| b| c$ is true, and we've shown that the condition can in fact be satisfied when $a| b | c$, the answer is all triples of the form $(a, ak, a \ell)$ for $a, k, l \in \mathbb{N}.$ $\square$