Nate,
I've worked in a body shop since I was 15 and I know for a fact that painting a Bali is NOT a good idea. It makes the handles smooth and slick and when you drop it, the paint begins to crack and flake off. Besides that, the PPG halequin, House of Kolors Kameleon, and Chromillusion are all VERY expensive, in the range of $40-$75 per Oz. To paint an entire car with it runs in the $3500 - $6000 range.
Poweder coating may work, but the heat required to use it would probably mess up the heat treating of the knife's blade.