Welcome to the Q&A Forum

• another advantage of this structure is the flexibility to change post titles without breaking links.

Well, I think that changing your title would break links and leads to another indexation. /12345.oldtitle/ is a different URL then /12345.newtitle/ or isn't it?

I would use the following
/%year%-%monthnum%-%day%-%postname%-%post_id/
/2010-08-04-titleofthepost-276762

Reasons:
Date for visitors, usually visitors need a clue whether your content is recent or not.
Postname for obvious reason
and ID for internal tracking and analysis

Furthermore using this structure makes it easy to analyse a site later in excel by text to column functions etc.

Plugins: I reccomend All in one SEO pack

In addition to Nemek:

Forums: find forums, that are related to your sites topic. Engange in a relevant and useful way. Put a link to your site in your profile. Promote special content (articles, lists, funny stuff) in your profile.

Blogs: Comment on related topics, but don't do the regular "Great article, thanks" stuff. Contact the author, ask for a guest article.

Twitter, Facebook, LInkedIn etc: Create a profile with your brandname (twitter.com/brandname) and link to your site. You might want to use a service like http://knowem.com/

Google Places: Create your places profile and link to your site.