I am a little shaky on how a 404 that returns the proper information should be setup. Right now, I have a 404 template that I note in my .htaccess as my 404 page. I was considering switching this to a page in EE's Pages module. Is this compatible with a proper 404 setup?
Your biggest point of attention should be the response header for your URL. EE will take care of setting it as a 404 response provided you have selected the template in use in the Global Template Preferences seen below. (Docs reference)
I'd recommend using a template rather than an entry + pages module. It's just simpler that way.
You don't need to use the Pages module, but you can use a channel entry to make the 404 page more dynamic, it just needs a dedicated template in order for the ExpressionEngine 404 handling to work correctly.
Often I'll simply duplicate my standard page template to be my 404 template and just hard code the entry in, instead of dynamically loading it from the URL.
You might find Guide to 404 Pages with ExpressionEngine useful: