Random name generator + some creativity goes a long way.
Paladin- Nossianiis (Noss)
Shaman- Kiatzu (Kia - should've thought that one through a little more, i'll admit.)
Also, i saw the words backwards thing mentioned earlier, that's a very good approach. open up a book, flip to a random page, put your finger on 1-2 words and reverse them, you'd be suprised with the results sometimes.
You might want to mention in the guide about masculine and feminine suffixes. In other words, names ending in "o" (male) or "a" (female), also "y" or "i"
Also, one thing I like to do is to make my alt names all resemble my main, it makes things much easier on friends and guildies. If you have a good strong first part such as "Denz" you can make many variations of the same name such as "Denzion, Denzy, Denzi, Denz, Denzian, Denzianne, etc.