How do I setup a proper 404 page? At present, my Drupal 7 website’s "Page not found" is 301 redirected to a custom 404 page.

However, I just checked the HTTP response code for a random URL and I noticed it 301 redirects to a custom "Page not found" page, but that page returns a 200 HTTP response code.

Shouldn't the page response header be 404?

If that's the case how do I fix the response code to 404 in Drupal 7?
Instead of using a 301 redirect to your custom 404 page, just go to

Admin > Config > System > Site Information

/admin/config/system/site-information


Enter your new path into the 404 error page box, and click "Save configuration".

You might also want to try the CustomError module:
https://www.drupal.org/project/customerror