Añadir un checkbox en la pantalla de edición para agregar una clase al título del post

Sí, es correcto, necesitas un Meta Box personalizado que cree los checkboxes en la pantalla de edición de entradas.

En este caso, son botones de radio, ya que solo necesitamos un valor.

El siguiente es el código que lo crea. Colócalo en el archivo functions.php de tu tema o crea un plugin sencillo para que esto sea independiente del tema.

/* Define el cuadro personalizado */
add_action( 'add_meta_boxes', 'wpse_61041_add_custom_box' );

/* Haz algo con los datos ingresados */
add_action( 'save_post', 'wpse_61041_save_postdata' );

/* Añade un cuadro a la columna principal en las pantallas de edición de Entradas y Páginas */
function wpse_61041_add_custom_box() {
    add_meta_box( 
        'wpse_61041_sectionid',
        'Color del título',
        'wpse_61041_inner_custom_box',
        'post',
        'side',
        'high'
    );
}

/* Imprime el contenido del cuadro */
function wpse_61041_inner_custom_box($post)
{
    // Usa nonce para verificación
    wp_nonce_field( 'wpse_61041_wpse_61041_field_nonce', 'wpse_61041_noncename' );

    // Obtiene el valor guardado, si no existe, se selecciona "default"
    $saved = get_post_meta( $post->ID, 'title_color', true);
    if( !$saved )
        $saved = 'default';

    $fields = array(
        'red'       => __('Rojo', 'wpse'),
        'green'     => __('Verde', 'wpse'),
        'blue'      => __('Azul', 'wpse'),
        'default'   => __('Predeterminado', 'wpse'),
    );

    foreach($fields as $key => $label)
    {
        printf(
            '<input type="radio" name="title_color" value="%1$s" id="title_color[%1$s]" %3$s />'.
            '<label for="title_color[%1$s]"> %2$s ' .
            '</label><br>',
            esc_attr($key),
            esc_html($label),
            checked($saved, $key, false)
        );
    }
}

/* Cuando se guarda la entrada, guarda nuestros datos personalizados */
function wpse_61041_save_postdata( $post_id ) 
{
      // verifica si es una rutina de guardado automático.
      // Si lo es, nuestro formulario no se ha enviado, así que no hacemos nada
      if ( defined( 'DOING_AUTOSAVE' ) && DOING_AUTOSAVE ) 
          return;

      // verifica que esto vino de nuestra pantalla y con la autorización adecuada,
      // porque save_post puede ser activado en otros momentos
      if ( !wp_verify_nonce( $_POST['wpse_61041_noncename'], 'wpse_61041_wpse_61041_field_nonce' ) )
          return;

      if ( isset($_POST['title_color']) && $_POST['title_color'] != "" ){
            update_post_meta( $post_id, 'title_color', $_POST['title_color'] );
      } 
}

^{código basado en esta Respuesta}

Cómo usarlo en el tema

Con las reglas CSS adecuadas en su lugar (h1.default, h1.red, etc.), donde quieras aplicar la clase de color al título (index.php, single.php, etc.), usa algo como:

<?php $title_color = get_post_meta( get_the_ID(), 'title_color', true); ?>
<h1 class="entry-title <?php echo esc_attr($title_color); ?>"><a href="<?php the_permalink(); ?>"><?php the_title(); ?></a></h1>

El trabajo de @brasofilo es genial, pero si no deseas hacer mucha codificación, puedes hacer el mismo trabajo desde Campos Personalizados. Está oculto por defecto. Puedes hacerlo visible desde Opciones de Pantalla. Crea un nuevo campo y nómbralo color y escribe el nombre del color en el campo valor. Luego, coloca este código en el header.php de tu tema, debajo de la etiqueta </head>.

<style type="text/css">
/*Reemplaza [nombre-del-color] con tu color, por ejemplo: red*/
#red {color:"red";}
#green {color:"green";}
#[nombre-del-color] {color:"[nombre-del-color]";}
#[nombre-del-color] {color:"[nombre-del-color]";}
</style>
    <?php
global $post;
$color = get_post_meta(get_the_ID(), 'color', true);
$id = "id="
?>

Luego, busca <h1 class="entry-title" y coloca este código dentro de él: <?php echo $id, $color;?>. Ahora, cada vez que quieras cambiar el color del título, elige color en el menú desplegable de campos personalizados y escribe el nombre del color en el campo valor.