I have seen a couple other posts about HDMI problems on the 2013 MBA but the authors never followed up with a solution....
Personally, I have used a Best Buy "Rocketfish" miniDisplayPort to HDMI adapter on my 2013 11" MBA without any problems. Have tried it on my 46" Sony LCD TV and also a cheap 13" LCD TV.
Maybe you could try a different cable and/or different monitor and see what happens? You could always get the Best Buy cable (it was the only one they carried), test it and return it for a full refund if it doesn't help.
Of course, your problem might also be related to the monitor. It might be set to "overscan" mode where it automatically crops the edges of the image. This is often the default setting on TV's. Look at the menus on the monitor and see if there's a setting that shows the entire image.