You can set an empty 1-pixel wide image with the desired height:
NSImage *image=[[NSImage alloc]initWithSize:NSMakeSize(1,30)];
[menuItem setImage:image];
Obviously you end up with titles that are offset 1 pixel to the right, though that may be acceptable if uniformly applied.