Over at vBSEO they've just published an article. Here's a quick summery of it. Go check it out :)

Title: Create a Custom vBulletin "404 Page Not Found" Page, and direct vBSEO to use it.
Author: Keith Cohen
Published: Wed, 07 Feb 2007 17:16:43 GMT
Full Article: http://www.vbseo.com/f34/create-custom-vbulletin-404-page-not-found-page-direct-vbseo-use-11288/


This will allow you to create a custom 404 Page Not Found page that uses your vBulletin templates, and includes your vBulletin header, navbar, and footer. All without modifying any vBulletin files.

Create a new template named custom_404 and paste the following content into it. (Feel free to customize, of course.)
Code:
$stylevar[htmldoctype]







$headinclude
Page Not Found - $vbphrase[x_powered_by_vbulletin]


$header
$navbar



Sorry, the page you have requested cannot be found.



You can try a search (http://www.vbulletin-fans.com/$vboptions[bburl]/search.php) if you are looking for something specific.


$footer



Then, create a file called 404.php in your site root, or forums root, and paste the following content into it. You will need to customize the code in red to point to the physical location of the misc.php file that comes with vBulletin.
Code:


Then, in your vBSEO Control Panel, for the "File Not Found" requests handling? setting, enter the following. Again, you will need to customize this to point to the actual physical location of the 404.php file that you created in the previous step.
Code:
/usr/home/username/public_html/404.php






(affiliate link)
http://www.vbseo.com/aff/banners/banner_vbseo_468x60_01.gif (http://www.vbseo.com/295_1_1_4/)

You haven't put the second code. :p
However, can I do this without vBSEO?

I think this requires vBSEO, check their full source to get the second code too I think.