Sebastian Delmont blogged recently about a flexible approach to handling permalinks that is an interesting compromise between numeric IDs and semantically rich textual slugs. Coincidentally, Aristotle Pagaltzis described the same thing last December.
To summarize: Combine the ID and the textual slug into a URL. Your app will resolve the URL based only on the ID part. The text is there to make users comfortable and the SEO-obsessed happy. So
/users/13-joshua would resolve to the same entity. Sebastian claims this happens in the database, but I'll note that
"13-josh".to_i returns the integer 13 so your Ruby code will be happy too.
I think that combining this naming scheme with a 301 permanent redirect to update stale names sounds fairly workable. You still have the problem of your del.ico.us bookmarks not being equated, but if this technique becomes common del.ico.us could notice the 301s and merge rankings of different URLs for the same thing. Maybe they even do that already - I don't use any bookmarking sites so I wouldn't know. I'm assuming the overhead for the slug comparison and redirect won't be an excessive burden to an app.
On another note, Dan Peterson put together a nice CRUD scaffolding generator. It creates controllers with the 7 CRUD actions (index, new, create, show, edit, update, destroy) and compatible view templates. If you're looking to get started with CRUD, using simply_restful with Dan's generator is a good way to go. Unfortunately there is barely any documentation on how to structure RESTful controllers. Note the opportunity for someone who wants to write some much needed docs!