Your example should work and there is a glitch in your proof. The product with an empty set is always again empty. In fact, you can construct the product of two categories $\mathcal{C}$ and $\mathcal{D}$ by taking pairs of morphisms $(f,g)$ with $f$ in $\mathcal{C}$ and $g$ in $\mathcal{D}$ and using the obvious composition.

As a side remark, while this is the usual definition of the product of two categories, your universal property is "evil" in the sense that one should not require the existence of a unique functor and commutativity on the nose but really use the 2-categorical structure available in $\mathbf{Cat}$.