Create category after theme setup and modify the default one

You can use wp_update_term to modify terms (even the default uncategorized) and wp_insert_term to update existing terms.

Here is a basic example that should get you there.

function add_category(){

    // Update Uncategorized Category (1)
    wp_update_term(
        1, 
        'category',
        array(
          'name' => 'New Category Name',
          'slug' => 'new-category-slug'
        )
    );

    // Insert New Category
    if(!term_exists('another-category')) {
        wp_insert_term(
            'Another Category',
            'category',
            array(
                'slug' => 'another-category'
            )
        );
    }
}

add_action('after_setup_theme', 'add_category');

This is tested and works.