Changing Permalinks without Breaking Backlinks?

Please forgive me, as I’m not a WP expert by any stretch.

I have a client who has a WP blog, but when it was up, the permalinks were set to default so his articles are all called using:

sitename.com/blog/p-11111

We’d like to change two things without destroying our back links:

First is that we don’t want to use the word “blog” as the name of the blog as it is currently set up.
I think this article addresses that issue:
http://codex.wordpress.org/Changing_The_Site_URL
Is that correct?

Second, I’d like to change the permalinks from calling articles by number to calling articles by name.

Ultimately, I’d like the blog URLs to look like this:
sitename.com/blog-name/this-is-the-article-title

Can we make that happen without destroying back links? This blog has been live for a few years, and I want to cause as little damage as possible.

Alternately, is there a way to employ a blanket 301 style redirect so that any links to the old site name.com/blog at least hit the homepage of the new one? Or is that just too sloppy?