they're quite common in brazil and spain (on the most touristic / surf beaches) - some times operated by companies, other times by the city hall itself
I'm guessing you aren't talking about Rio. I live in the Zona Sul and haven't come across lockers on the beach (though I had the idea literally a few days ago). If they do exist here, whereabouts can I see them?