Attachment Page Permalink/URL Rewrite Issue. How to change the actual rewriting?

To provide an answer to your first question and for future reference to tackle the problem you described with the slug already being in use when you first uploaded an attachment to the same parent. The following code will get rid of this ‘annoying’ thing (annoying in some use cases).

This code rewrites the slug of the attachment upon uploading to add a prefix (or suffix) to the slug. In that case you have less chance of getting in the way of page slugs in the future.

add_action('add_attachment', function($postId) {
    // get the attachment post object
    $attachment = get_post($postId);
    // get the slug for the attachment
    $slug = $attachment->post_name;
    // update the post data of the attachment with an edited slug
    wp_update_post(array(
        'ID' => $postId,
        'post_name' => 'media-'.$slug, //adds a prefix
        //'post_name' => $slug.'-photo', //adds a suffix
    ));
});

I hope this will help anyone.