Okay, here is my solution. No need to build a new DejaVu package, no need to install defoma, new font libraries, or anything like I was trying before.

Install the ttf-dejavu package from extras. If it doesn't show up in the package manager (I can't remember it it does or not), install rootsh (you are going to need it later anyway) and open the terminal. Type this line:

Now, still in terminal cp (or ln if you want to save some space) the dejavu file to wesnoth, like so:

If you want to cp (I did):

Linking should look like this:

You might get a warning when you link if the file already exists. Remove it (rootsh rm /usr/share/games/wesnoth/fonts/DejaVuSans.ttf) and try again.

Hopefully this works for you. It does for me, but I am running a newly built 1.4.5 version that I compiled. If anyone is interested, I should be able to release this version somewhere. It fits very well on the screen, runs smoothly, music works (with a patched libsdl-mixer), and hasn't crashed that I have found.