I would use the wp_title filter hook:
function theme-slug_filter_wp_title( $title ) {
if ( is_404() ) {
$title = 'ADD 404 TITLE TEXT HERE';
}
// You can do other filtering here, or
// just return $title
return $title;
}
// Hook into wp_title filter hook
add_filter( 'wp_title', 'theme-slug_filter_wp_title' );
This will play nicely with other Plugins (e.g. SEO Plugins), and will be relatively forward-compatible (changes to document title are coming soon).
EDIT
If you need to override an SEO Plugin filter, you probably just need to add a lower priority to your add_filter() call; e.g. as follows:
add_filter( 'wp_title', 'theme-slug_filter_wp_title', 11 );
The default is 10. Lower numbers execute earlier (e.g. higher priority), and higher numbers execute later (e.g. lower priority). So, assuming your SEO Plugin uses the default priority (i.e. 10), simply use a number that is 11 or higher.