Actually if we just let the objects in Cat be structures that are the right "shape" but don't necessarily follow the laws (call this Cat'), then we can prove the laws by finding an functor that is faithful and one to one on objects, to a object in Cat' that is in fact is a category.