We have several used gear shops locally, which also sell climbing shoes. I'm looking to start climbing and I am considering buying used shoes to save cost. Is it ever safe to buy used shoes, and if so, what would indicate that a pair is no longer "safe"?
Your life will not be at risk from used shoes. No.
But you will run a serious risk of getting athlete's foot. This happened to me and it took six months to get rid of. Beware.
You shouldn't buy used safety equipment (ropes, harnesses, carabiners, etc) because you don't know if the previous owner handled them properly (maybe they splashed bleach on the rope?). But shoes aren't really considered "safety related" - if the shoes did fail in a climb, it would be no different than having your foot pop off because of bad footwork. Which happens frequently, and is something you should assume might happen - that's why you have a rope and harness that you trust.
Safe? Yes. As in your life usually doesn't depend on them. Safe, as in a safe buy? Also yes.
When looking at used climbing shoes it really helps if you take someone along who knows what to look for and/or knows the shoes themselves. If you know what they look like new then you know what they should look like.
Specifically, check the seams and make sure they aren't coming apart. Especially the seam around the thickest part of rubber on the soles. If it looks like it starting to pull away at all stay away.
Check the rubber on the bottom. If it has deep gouges or long cuts in it, then the previous owner probably didn't take care of them and might have even hiked in them.
Often times you can find shoes in nearly new condition this way. Plenty of people make the mistake of buying everything and finding out they don't like rock-climbing, or picking shoes like they would any other shoes and have to bring them back because they don't fit right.
I would highly recommend you try to find somewhere to rent the shoes and try them out first. Or go to an indoor gym and try them.
For the fit, they should be sock tight (which is why I don't wear socks with them). Your first time wearing them, your feet should be in pain after climbing in them for an hour or two.
For your first pair I recommend a mostly flat sole, for "all-around" use. They usually do alright in any situation and they are often times cheapest (not always). As you get more experience you will learn what you need.