I don't know how much of a 'problem' you are concerned about with solo diving. For example, at least one other poster indicated that in Curacao he drove off with tanks and nobody bothered him, to solo dive. So, unless you intend to announce your intent to solo dive, Curacao might be viable.
The shore diving places I'm aware of are:
1.) Bonaire - the big one!
2.) Curacao.
3.) Cayman Islands - Grand, Little and Brac each have something, I think.
4.) Roatan but mainly at certain spots, such as Cocoview and Reefhouse Resort.
5.) Lauderdale by the Sea in Florida.
6.) Blue Heron Bridge.
I don't know whether & to what extent enforcement officials are apt to bother you though.
Richard.