Train 2hb,
http://wiki.project1999.com/Baton_of_Faith is incredibly cheap (or it was when I was active anyway).
Frug's approach is solid, but you may not always have decent weapons of every type available. When I was levelling my paladin I polished lagging weapon skills while LFG soloing in his 30s and 40s, doesn't really matter if it costs a full manabar of healing to get thru the fight with an inferior weapon and dex jewelry when you're mostly after skill-ups anyway.