"these "embed the title" schemes are just abusing URLs as storage for content that simply should not be in the URL."

I don't look at it this way. I think readable URLs are part of the way the web was designed - this idea that URLs map to individual documents and not to an application that has to translate between the URL and the resource it represents.

Quite to the contrary: Having a database id in the URL is sticking model/data layer logic where it doesn't belong - the view layer of the APP.

As for the permalink problem on changing titles you can simply store a history of redirects for every title that the article has ever had to the current, active URL.