Query Custom Post Type and Output to timeline

Assuming this to be the primary question:

How would i fill the “empty” years with li elements and add classes
depending on years?

You don’t really have a “query” problem, just a PHP/markup one. You need to track you years independently of your query. Below is proof-of-concept code for doing that. I did not try to make it output the precise markup you require. Be aware that the Loop is very sensitive to post order and that you need 'ignore_sticky_posts' => true or post dates will be out of order and the loop will not work correctly. It will stop at the year of the last post, not necessarily at “this year”.

$year = 2000;
$qry = new WP_Query(
  array(
    'post_type'=>'post',
    'posts_per_page'=>-1,
    'orderby'=>'date',
    'order'=>'ASC',
    'ignore_sticky_posts' => true
  )
);

if ($qry->have_posts()) {
  while ($qry->have_posts()) {
    echo $year;
    if (date('Y',strtotime($qry->post->post_date)) == $year) {
      the_title();
      $qry->the_post();
    } else {
      echo 'no posts';
      $year++;
    }
    echo '<br />';
  }
}