You're right, it's the object-oriented parts that are throwing you off.

The nav menu call should be:

wp_nav_menu(array(
    'theme_location' => 'menu-top',
    'container'      => 'ul',
    'menu_class'     => 'header_nav_ul',
    'menu_id'        => 'header_nav_id',
    'depth'          => 0,
    'walker'         => new my_walker_nav_menu_start_el,
));

• no parentheses () after the name of the walker.

The walker itself needs to extend Core's Walker_Nav_Menu, and there is no add_filter() call for it.

// Extend the existing Core class, to build on its functionality
class my_walker_nav_menu_start_el extends Walker_Nav_Menu {
    // Make the function public so it can be called elsewhere
    public function my_walker_nav_menu_start_el($item_output, $item, $depth, $args) {
        if ( $depth == 1 ) {
            $item_output = preg_replace('/<a /', '<a class="level-1-menu" ', $item_output, 1);
        } else if ( $depth == 2 ) {
            $item_output = preg_replace('/<a /', '<a class="level-2-menu" ', $item_output, 1);
        }
        return $item_output;
    }
}
// Remove the add_filter() call as it's not used

Just make sure the links don't have any other class, or else you'll end up with links that have 2 "class" attributes.

You're right, it's the object-oriented parts that are throwing you off.

The nav menu call should be:

wp_nav_menu(array(
    'theme_location' => 'menu-top',
    'container'      => 'ul',
    'menu_class'     => 'header_nav_ul',
    'menu_id'        => 'header_nav_id',
    'depth'          => 0,
    'walker'         => new my_walker_nav_menu_start_el,
));

• no parentheses () after the name of the walker.

The walker itself needs to extend Core's Walker_Nav_Menu, and there is no add_filter() call for it.

// Extend the existing Core class, to build on its functionality
class my_walker_nav_menu_start_el extends Walker_Nav_Menu {
    // Make the function public so it can be called elsewhere
    public function start_el($item_output, $item, $depth = 0, $args = array(), $id = 0) {
        if ( $depth == 1 ) {
            $item_output = preg_replace('/<a /', '<a class="level-1-menu" ', $item_output, 1);
        } else if ( $depth == 2 ) {
            $item_output = preg_replace('/<a /', '<a class="level-2-menu" ', $item_output, 1);
        }
        return $item_output;
    }
}
// Remove the add_filter() call as it's not used

Just make sure the links don't have any other class, or else you'll end up with links that have 2 "class" attributes.