My first thought was Bali as well, probably since I was there a few weeks ago. Tulamben would perfectly fill the OP's requirementsexcept for the beach. When she says "beach" I assume she means a sandy one, not a rocky one. That also rules out most of Bonaire, as has been pointed out, except for
Harbour Village and perhaps one or two others. A nice beach is probably the kiss of death for nice shore diving, since it attracts the hordes, so it becomes an either-or proposition. While Bonaire is not my first choice for diving, it is my first choice for vacation, and I always stay at Harbour Village. There is nothing quite like strolling down a gently sloping sandy beach to find quality diving. That said, the diving in front of Harbour Village is not the best on the island, and it takes a bit of a swim to get to even decent diving there.
Back to Bali. There are certainly nice beaches, but if you want to laze around and dive when you feel like it, you might have to settle for a hammock or lounge chair near the rocky shoreline. I recommend
Mimpi Tulamben. If your budget allows, the oceanside villas are nice and the diving is quite good right out front. But you can do it more economically at Mimpi, or much more economically elsewhere in Tulamben. The entry over the rocky shoreline can be a bit of a nuisance, but otherwise the diving is as easy as it gets, usually.
The nicest sandy beach I have ever seen next to a dive spot is Flinder's Cay. It is deserted except for an unmanned weather station and is only accessible by boat, since it sits well outside the Great Barrier Reef in the Coral Sea. Nesting turtles and birds, a beautiful crescent of sand, and great diving.