How to fetch only media that was already attached to a post/page?

A similar approach to your post_parent idea is to add a filter to posts_where:

function bbg_filter_out_non_attachments( $sql ) {
    global $wpdb;

    // Maybe do some conditional logic to decide whether to filter this query, then...
    return $sql . " AND $wpdb->posts.post_parent != 0 ";
}
add_filter( 'posts_where', 'bbg_filter_out_non_attachments' );

Another technique is to do a manual query for post IDs with no post_parent, and then pass it to post__not_in:

$ad_ids = $wpdb->get_col( $wpdb->prepare( "SELECT ID FROM $wpdb->posts WHERE post_parent = 0 AND post_type="attachment"" ) );
$query_args['post__not_in'] = $ad_ids;
// etc

If you don’t like the idea of mucking around directly with SQL, you could also piece something together that adds a piece of postmeta to every item uploaded through the Media Library (instead of on a new post), and then include a meta_query parameter in your WP_Query. Note, however, that this isn’t going to be anywhere near as efficient as simply looking for post_parent (which is data that already exists, and does not require a table join).