How do I sort by a custom field without manually creating a new page?

At the top of category.php template in your theme's root directory, add the following to add your custom sort field to the query:

<?php
function is_valid_custom_sort_field($field)
{
    // implementation left as an exercise for the questioner
    return true;
}
if ($_REQUEST['sort_custom_field'] && is_valid_custom_sort_field($_REQUEST['sort_custom_field'])) {
    query_posts($query_string . '&orderby='.$_REQUEST['sort_custom_field']);
}

See: http://codex.wordpress.org/Function_Reference/query_posts

If your theme doesn't have a category.php, here is a simple default template to base it on (copied from the included twentyten theme):

<?php
/**
 * The template for displaying Category Archive pages.
 */

get_header(); ?>

        <div id="container">
            <div id="content" role="main">

                <h1 class="page-title"><?php
                    printf( __( 'Category Archives: %s', 'twentyten' ), '<span>' . single_cat_title( '', false ) . '</span>' );
                ?></h1>
                <?php
                    $category_description = category_description();
                    if ( ! empty( $category_description ) )
                        echo '<div class="archive-meta">' . $category_description . '</div>';

                /* Run the loop for the category page to output the posts.
                 * If you want to overload this in a child theme then include a file
                 * called loop-category.php and that will be used instead.
                 */
                get_template_part( 'loop', 'category' );
                ?>

            </div><!-- #content -->
        </div><!-- #container -->

<?php get_sidebar(); ?>
<?php get_footer(); ?>