I wouldn't recommend having the "pretty" part not validated. It can cause some serious issues with google & duplicate content and if someone wants to be malicious they can create a bunch of fake urls that essentially point to the same page, or even worse if they receive enough links they can be indexed at the new "fake" url. A similar thing happened to a newspapers website but I can't recall who of the top of my head.

Another potential solution & my preferred method is whenever a change is made that would affect the url of a page. Update a "legacy" table with the old url and the location of the new url, next time a 404 is going to be thrown do a search against the database & redirect accordingly if a new url is found. I rolled this approach into https://github.com/leonsmith/django-legacy-url and whilst it's not polished it's by far the easiest & probably most automatic/maintainable solution I have found.