I've been in that spot for a long time and my excuse always was that vegetarianism would be too inconvenient.
Around the end of last year it finally clicked. The inconvenience excuse is plainly wrong in many cases AND being a vegetarian in just these cases is still a good thing!
I resolved to eat vegetarian whenever it is not inconvenient. This turned out to be almost always. Especially easy are restaurants and ordered food. When in a supermarket I never buy meat which automatically sets me up for lots of vegetarian meals.
I'm currently eating vegetarian on ~95% of my meals. As a bonus I don't have a bad conscience in the few cases where I eat meat.
Actually, I just did something similar.
I already keep daily logs about what I did during the day (e.g. if I had an exercise), so I added not eating meat to the list of recorded variables. This step was trivial. But now, whenever I am choosing a meal, I remember that I will have to put it on the record. And somehow this trivial inconvenience makes me choose the vegetarian meal more reliably than previously.
I started recording this two weeks ago. First week there was no difference, but the second week I ate vegetarian food for the whole week. I only broke the chain today, because we already had some pre-made soup containing meat at home.
Neal Stephenson's The Diamond Age takes place several decades in the future and this conversation is looking back on the present day:
I'm not sure if I agree with this characterization of the current political climate; in any case, that's not the point I'm interested in. I'm also not interested in moral relativism.
But the passage does point out a flaw which I recognize in myself: a preference for consistency over actually doing the right thing. I place a lot of stock--as I think many here do--on self-consistency. After all, clearly any moral code which is inconsistent is wrong. But dismissing a moral code for inconsistency or a person for hypocrisy is lazy. Morality is hard. It's easy to get a warm glow from the nice self-consistency of your own principles and mistake this for actually being right.
Placing too much emphasis on consistency led me to at least one embarrassing failure. I decided that no one who ate meat could be taken seriously when discussing animal rights: killing animals because they taste good seems completely inconsistent with placing any value on their lives. Furthermore, I myself ignored the whole concept of animal rights because I eat meat, so that it would be inconsistent for me to assign animals any rights. Consistency between my moral principles and my actions--not being a hypocrite--was more important to me than actually figuring out what the correct moral principles were.
To generalize: holding high moral ideals is going to produce cognitive dissonance when you are not able to live up to those ideals. It is always tempting--for me at least--to resolve this dissonance by backing down from those high ideals. An alternative we might try is to be more comfortable with hypocrisy.
Related: Self-deception: Hypocrisy or Akrasia?