You need to add a so called Area to the template used by the 404-page. Without an Area you won't be able to add the block to the 404-page.

Instructions for Elemental theme

If you use the default concrete5 Elemental theme and you haven't copied the theme to your application folder:

1. Copy /concrete/themes/elemental to /application/themes/custom
2. Open /application/themes/custom/page_theme.php and change the namespace to "Application\Theme\Custom"
3. Also change the name of the Theme in the method "getThemeName" to "Custom"
4. Open /application/themes/custom/css/main.less and change line 6 to: @import "../../../../concrete/css/build/core/include/mixins.less";
5. Go to Dashboard / Pages & Themes and install the Custom theme.
6. Activate the theme.

Once you've copied the theme to your application folder and it has been activated, do the following:

1. Open /application/themes/custom/page_not_found.php
2. Add code so it reflects the example below:

<?php
defined('C5_EXECUTE') or die("Access Denied.");
$this->inc('elements/header.php'); ?>

<main>
    <div class="container">
        <div class="row">
            <div class="col-sm-9 col-sm-offset-3">
                <div class="jumbo">
                    <h1><?php echo t('404 Error')?></h1>
                    <p><?php echo t('Page not found.')?></p>
                   
                    <?php
                    $a = new Area('Content');
                    $a->display($c);
                    ?>
                </div>               
            </div>
        </div>
    </div>
</main>

<?php  $this->inc('elements/footer.php'); ?>

Now you can add the block to the 404-page!