Rewriting post slug before post save

The following is to be taken more as a proof of concept rather than a copy/paste-ready solution.
That being said, this is how you’d go about it:

The save_post action runs whenever a post is updated or created. You can hook a callback function to it using add_action.

Hence, your case would have to look something like this:

// initial hook
add_action( 'save_post', 'wpse105926_save_post_callback' );

function wpse105926_save_post_callback( $post_id ) {

    // verify post is not a revision
    if ( ! wp_is_post_revision( $post_id ) ) {

        // unhook this function to prevent infinite looping
        remove_action( 'save_post', 'wpse105926_save_post_callback' );

        // update the post slug
        wp_update_post( array(
            'ID' => $post_id,
            'post_name' => 'some-new-slug' // do your thing here
        ));

        // re-hook this function
        add_action( 'save_post', 'wpse105926_save_post_callback' );

    }
}

What might be a bit confusing in the above is the un- and rehooking of the function from within it. This is required, since we call wp_update_post to update the slug, which in turn will trigger the save_post action to run again.

As an aside, if you want WP to automatically generate the new slug based on the post title, simply pass an empty string:

wp_update_post( array(
    'ID' => $post_id,
    'post_name' => '' // slug will be generated by WP based on post title
));