Template for all categories of a custom post type?

The name you are using for taxonomy isn’t allowed. register_post_type() $taxonomy parameter says

$taxonomy

(string) (required) The name of the taxonomy. Name should only contain lowercase letters and the underscore character, and not be more than 32 characters long (database structure restriction).

Default: None

So, you need to change the name cat-listings to something else( I will assume cat_listings for the rest of the answer)

Now let’s visit your questions one by one.

  1. So when I visit http://www.domain.com/listings/cat_listings/lease I get a 404 (does this mean that this page is not possible to have? or because I am missing a template.

It’s possible to have Permalink structure like that. If you create a term named lease under taxonomy cat_listings, the default url structure will be

http://www.domain.com/cat_listings/lease

If you want to add a segment named listings before that, you have to pass rewrite arguments like this

$catProjectsArgs = array(
    'label' => __('Availability', theme_domain()),
    'sort' => true,
    'show_ui' => true,
    'show_admin_column' => true,
    'hierarchical' => true,
    'update_count_callback' => '_update_post_term_count',
    'query_var' => true,
    'rewrite' => array( 'slug' => 'listings' )
);

By the way, there is no parameter named args, I’ve removed that.

  1. Now I know I could create a page for each and have them have their custom template pages but the issue I have with this is if my client ever wants to add another category a page and page template has to be created.

It should be pretty clear which template file you have to use, if you look at the template hierarchy image. Here’s a cropped version just for custom taxonomy

template hierarchy for custom taxonomy

If you want to apply a single template for all terms under cat_listings, just create template file taxonomy-cat_listings.php. If you want to create separate template file for one of the terms that you add later, say lease, you need to create template file taxonomy-cat_listings-lease.php and so on.