wp_nav_menu with WP as pure CMS

I know I can change WP to use nice permalinks to get www.example.com/wordpress/about but I’d like to customise it further so that the link would read www.example.com/about e.g. skip the wordpress install location.

Rather than “skipping the location”, point your domain to the location.
Or install WP to your root, respectively.

You could obviously do some rewriting as well, but why go the long way if the solution is simple?

As for pretty permalinks:
However you go about it, this is a necessary step on the way.

Hence set your permalink structure to something along the lines of /%year%/%postname%/.

There used to be performance downsides to using just /%postname%/, which have been fixed with 3.3, but I tend to still not use that only.
Pages will ignore /%year%/ anyway. And should you ever decide to use the blog functionality as well, I don’t find a year structure hurtful. Up to you.