Come out here to California. Stay at one of the cheap motels in San Diego for $36 per night. There is lots of diving there one of the local boats runs two tank trips to the local wrecks for $50. Lots of other tourist things to do.
And then closer to my house is Catalina Island. Lots of very good divng there for just the cost of air. Also two boat operators there. Very low cost hotel is this one
Welcome to the Hermosa Hotel I've been so cheap as to split one of the $25 rooms between three divers. (less then $10 per night) No place can beat that price and diving and airfill are walking distance. (cars are mostly not allowed on the island)
What this really means is that you should talk to the local divers. They all know about cheap local diving. People only go to the expensive places because they don't know the others. Use the Internet and these forums