Preventing index.php?category_name=something from redirecting

This should work:

add_action( 'init', 'wpa12742_init' );

function wpa12742_init(){
  add_rewrite_rule( 'category/(.+?)/(\d{4})/?$', 'index.php?category_name=$matches[1]&year=$matches[2]', 'top' );
  add_rewrite_rule( 'category/(.+?)/(\d{4})/page/(\d+)/?$', 'index.php?category_name=$matches[1]&year=$matches[2]&paged=$matches[3]', 'top' );
}

EDIT

On second thought, that’s not enough, since you’ll get caught by redirect_canonical().

Add this too:

add_filter( 'term_link', 'wpa12743_term_link', 10, 3 );

function wpa12743_term_link( $link, $term, $taxonomy ){
  if('category' != $taxonomy && !preg_match( '@^\d{4}$@', get_query_var('year') ) )
    return $link;
  return trailingslashit( $link ) . get_query_var( 'year' );
}