How to display message (with switch_theme hook) after deactivating My theme?

It’s impossible, because after deactivation your theme isn’t even loaded!

It’s possible, but hacky. Essentially, we unset the action param, load in the themes admin page & then exit before the redirect-on-success occurs.

add_action( 'switch_theme', 'wpse_60972_theme_deactivate_message' );
function wpse_60972_theme_deactivate_message()
{
    $msg = '
    <div class="error">
        <p>Your theme has been DEACTIVATED</p>
    </div>';

    add_action( 'admin_notices', create_function( '', 'echo "' . addcslashes( $msg, '"' ) . '";' ) );

    unset( $_GET['action'] );
    require ABSPATH . 'wp-admin/themes.php';
    exit;
}

If the code you posted is verbatim, may I ask why you want do as such? WordPress has it’s own notices for activation & deactivation.