I get as much as I can off manually (forceps, scalpel etc), then soak in a dilute solution of an enzymatic washing powder (for clothes), I check regularly, teasing off tissue as it comes loose, some will dissolve and become gunk on the container bottom!
Are they fresh or is the flesh already fixed? You can soak them in water for a few days to loosen up the tissue either way, then try Jean's tricks, and/or extract the beaks, then simmer gently in dilute KOH for a few minutes at a time and tease bits away as they come loose. Works well for cleaning radulae too.
I guess this was all for not. One of the many people passing through the apartments through my beaks away!!! I guess such a small bag in the freezer was taking up too much space. I am not too happy with this person because I did have a beak of a pelagic octopus that I will probably never see again!!
It might be too late, but if you need to do it again in the future I would suggest using either proteinase K or collagenase digestion. They are very good at digesting tissue but leave keratinised parts alone - the beak should be resistant.
Plus you'll have the advantage of being able to isolate the DNA from the liquid left over which you can do all sorts of cool things with...