How do I implement a VIDEO gallery like gallery formatter but with videos?
If you're able to switch to a module other than video_embed_field I'd highly recommend the Media module along with the Media Gallery module.

You'll also want Media Youtube, I've used those three together quite a bit and they're very good.

I'd also recommend installing Colorbox to take advantage of the built-in lightbox features.