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:

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

    <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>
                    $a = new Area('Content');

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

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