Using wp_list_pages to create 2 lists of pages and include and exclude some of them depending on their category

One quick way of doing it without having to set up multiple loops would be to use the get_posts() function and grab all pages, then check through them with in_category() and split out pages that are in the category and pages that are not.

You can then run through the 2 groups of pages separately in your ULs with a simple foreach loop.

<?php $args = array(
    'post_type' =>  'page',
    'post_status'   =>  'publish',
    'numberposts'   =>  -1
);

//Pull pages into an array
$all_pages = get_posts($args);

//Create empty arrays to populate with filtered pages
$in_category = array();
$ex_category = array();

//loop through the page array
foreach($all_pages as $post) {
    //Set data from the current page as globals,
    //to enable WordPress function tags
    setup_postdata($post);

    //Build the format of the link to be returned
    $link_format="<li><a href="".get_the_permalink().'">'.get_the_title().'</a></li>';        

    //Check whether the page is in the category and
    //send this link to the relevant array
    if(in_category(4)) {
        $in_category[] = $link_format;
    } else {
        $ex_category[] = $link_format;
    }   
};

//Restore postdata to before we set it to the current post
wp_reset_postdata(); ?>

<ul class="links_in_category_4">
    <?php foreach($in_category as $cat_link) echo $cat_link; ?>
</ul>

<ul class="links_not_in_category_4">
    <?php foreach($ex_category as $cat_link) echo $cat_link; ?>
</ul>