If the tank has no plants ATM. Then you can just remove all the algae by hand. Remove any rocks or decore and scrub them too. Remove the top layer of algaefied gravel. Do a 50% water change. Blackout the tank for 3-5 days, and then after that keep the lights on only a couple hours a day and keep up the weekly 25-50% water changes.
Adding plants to this algaed tank most likely will not solve the problem. I say that based on the story in your post.
As for the pleco, there are lots of kinds. Only a couple really live exclusively on algae, and even then it has to be the type that particular pleco will eat. Most likely he starved to death. Most plecos prefer some driftwood to gnaw on, and a diet of algae wafers and zuchini will keep em happy.
