How to verify signed bitcoin messages on my own website?
You don't need all of bitcoind just for this functionality. Look at the code on the brainwallet.org page you posted: http://brainwallet.org/js/bitcoinsig.js

It seems like you could take this exact code and implement it on the server-side with a JavaScript interpreter such as node.js.

It depends on the programming language you're using but I'm sure this functionality is available in most of the bitcoin libraries: https://en.bitcoin.it/wiki/Software#Libraries