Why isn't the 404.php page working?

Hello,

I recently created my own theme but I can’t get the 404.php file to start working.

Whenever I go to a page which doesn’t exist I just remain on the page I previously on, e.g: http://domain.com/djdjd redirects > http://domain.com/djdjd/

Here is my 404.php
http://pastebin.com/Pt5rg0vb

I’d really appreciate some help as I’m totally lost.

Thanks!