If you are committed to running the HDMI cables through the walls come hell or high water, then you can take more risks than if you are not willing to absorb all possible costs. The likelihood of your coax being stapled to studs will depend on how old the house is and whether the cabling was installed during its construction.
If you are willing to risk the loss of functionality of the coax, then begin by cutting the connector off and attaching a pull string to the coax. In fact, to best avoid snags, you should make a tiny loop out of the cut coax's center conductor and thread a pull string through that, so it won't enlarge the circumference of the coax and won't form a snag point when pulled forward. You should also tape that junction over just in case you have to "punt" and pull the coax back and don't want it to snag in the other direction. Plus, by doing it that way, you'll wind up with two strings pullers, so if you are unsuccessful at pulling the HDMI cable through the wall, which can easily happen because of the HDMI connector, you will still have a remaining pull string which you can use to either pull additional pull strings or to pull an ordinary coax back.
If you find that you cannot pull a cable with an HDMI plug on it through the wall, you might be able to pull two Cat 5 wires and use an HDMI-to-Cat5 adapter pair.
Edited by AntAltMike - 4/21/13 at 10:09am