Display 2nd category, only once, as sub-heading, in the loop

I have a Custom Post Type ("Rental"). I am using the code from this article I found to display Rental custom posts on a page, with the Categories of a custom Taxonomy ("Region") as headings between the posts that belong to that Category. For example, it outputs this structure:

• Region Category #1
  
  
  
  • Post #1
  
  
  • Post #3
  
  
  • Post #4
  
  
  
  


• Region Category #2
  
  
  
  • Post #2
  
  
  • Post #5
  
  
  • Post #6
  
  
  
  

I am now trying to add subheadings of Categories from a second Custom Taxonomy ("Property"), but only once in the loop. I'm not sure where to start (do I need another foreach loop, or can I add to the existing one?), any help or direction would be much appreciated.

For example, I'm looking to get this output structure:

• Region Category #1
  
  
  
  • Property Category #1
    
    
    
    • Post #1
    
    
    
    
  
  
  • Property Category #2
    
    
    
    • Post #3
    
    
    • Post #4
    
    
    
    
  
  
  
  


• Region #2
  
  
  
  • Property Category #3
    
    
    
    • Post #2
    
    
    • Post #5
    
    
    
    
  
  
  • Property Category #4
    
    
    
    • Post #6
    
    
    
    
  
  
  
  

This is the code I have so far:

  <?php
    // get all the categories from the database
    $cats = get_categories('taxonomy=region');
    // loop through the categries
    foreach ($cats as $cat) {
        // setup the cateogory ID
        $cat_id= $cat->term_id;
        // Make a header for the cateogry
        echo "<h1>".$cat->name."</h1>";  
        // create a custom wordpress query
        $args = array(
            'tax_query' => array(
              array(
                'taxonomy' => 'region',
                'field' => 'slug',
                'terms' => ".$cat->name."
              )
            )
        );
        $query = query_posts( $args );
        // start the wordpress loop!
        if (have_posts()) : while (have_posts()) : the_post(); ?>
            <?php // create our link now that the post is setup ?>
            <p><a href="<?php the_permalink();?>"><?php the_title(); ?></a></p>

        <?php endwhile; endif; // done our wordpress loop. Will start again for each category ?>
        <?php wp_reset_query(); ?>
  <?php } // done the foreach statement ?>