The description is a little vague, but I think you are describing a second-order Latin cube. As I remember from my combinatorial design class, there are efficient algorithms for generating them, none of which I have handly at the moment. A google search would probably be useful at this point.