I suggest starting with countries like Georgia, Lithuania, Estonia, Hungary, etc. If you can find somewhere that is slightly behind the curve technologically (lots of extra switching and routing), has a lower international fraud rate (as the phone company may assume fraud if you're trying to call Lagos, Nigeria, for example), and has a possibility of English speakers, then you're good.
What could work well is find numbers for large businesses in other countries. Look up the business on the nation's stock exchange and call. That way, if the operator is inclined enough (after enough attempts) to try to "investigate" why you're calling, you can claim you're looking at investing in these businesses.
As RB said, though, it's hard to find a phone co that still accepts currency, connects int'l calls, and is reputable enough to refund you. If your local phone CO has payphones, or has bought out the old SW Bell, Verizon, or Millenium phones, you may be in luck. If you are in an area with an airport of any size, train station, or Greyhound terminal, this is a great place to start. You being at a travel area would also explain to an operator why you're using a payphone, for example (damnit, I left my cell phone at the airport!)
