ErrorDocument 404 http://example.com/404.php
Actually, the above is an 'external' location for the file (even though I'm guessing it's on your website) so Apache will correctly
send a '302 Found' (AKA Undefined) redirect status code, so in this case you will have to set the 404 header on the error page... (This is a redirect
ErrorDocument 404 /404.php
Is an 'internal' location, so rather than sending the browser there, Apache 'gets' the page and serves the information from it, so a 404 Not Found will be served to the visitor... (This is a rewrite
IMO the safest thing to do is use the server relative path (starts with a / as above) and go ahead and set the 404 on the PHP too... It's a bit of double coverage, and as long as you have it correct then it doesn't hurt. I actually have a set of custom error page 'starting points' that contain certain things I use on them, such as the PHP status code header for the error, and noindex,nofollow,noarchive robots meta tags, a 'the URL: http://www.example.com/url-here.html has been disconnected or is no longer in service' message (actually, I think that one's my answering machine, but I'm sure you get the point, and I think that one's going on my new 404 pages, because I like it. LOL.), a link to the home page for sure (and usually a few 'key' pages I think people might like to visit) etc. Then I just put a different template on them for different sites.
Also, it's usually recommended to always check error page headers, which can be done with a FireFox Plugin (Live headers, I think) or (what I usually use since I've been using it for years) is the server header check here in your control panel... Go to the control panel link at the top of the page, give it a click, turn left, pause to look at the neat little picture above the calendar for a second, look down at the bottom of the links on the left, click the second one up where it says 'server headers', copy and paste a broken link from your site in the box, hit 'submit' and you'll know what code the bots are getting for that page... Sometimes it's a good idea to do on pages you think are supposed to work too, just to see what's being sent. :)