The answer is almost certainly Thailand, in particular Ko Tao, the PADI factory of the world. An end-to-end course that gets you the standard PADI Open Water license will set you back roughly 9800 baht (~$310 at time of writing); if you're happy with the far more limited PADI Scuba Diver course, you can complete that for 7000 baht (~$225) at this randomly chosen dive shop. Chuck in food and accommodation for around 1000 baht/day all-in for 3-4 days (you can squeeze by for less if you're
a cheapskate frugal), and you can complete your course for under $500.
A close second is Malaysia, where diving is about the same price due to furious competition, but food and accommodation are generally pricier. I'd imagine the Philippines are in roughly the same price bracket as well. Diving in Indonesia is generally not as affordable simply because the diving off Bali is not that great and the places with great diving (Bunaken etc) are in harder-to-reach locations.
All that said, diving is one of those things where you definitely don't want to look for price alone, this is life support equipment we're talking about here and you want to make sure it's properly maintained. (When I lived in Singapore, I ended up buying my own gear, just so I could maintain it myself.) So do your homework and pay a little extra to find a dive shop with a clue, here's a handy article with some tips. (TL;DR: Check online reviews, go visit, chat with the instructors and look for certifications, general cleanliness, gear appearance and maintenance schedule.)