You can shoot any issued M16/M4 left or right handed. You will be allowed to shoot left handed. The first few days on the range your PMI will have everyone do a little test to determine which of your eyes is dominant. To many peoples surprise, including my own, your dominant eye doesn't always correlate to your dominant hand. Before bootcamp my left was dominant in every single thing I did. After the little eye test I was told to shoot right-handed. It was a little uncomfortable at first but I eventually ended up shooting a 242 so it worked out.
I'm a lefty and left shooter as well. I know that the M16 can be shot either side, just have to adjust the sights to your style.
I'm not a Marine yet, but according to my recruiter, if I wanted to get a left handed weapon I'd have to get a regimental waiver and some other very unnecessary paperwork.