As Ben said, you could get away with sandpaper or a diamond plate to change the profile.
And there are lots of ways for creating new handles, depending on the shape of tang and the result you want. Most probably you'd need some wood (unless you are going to use micarta or horn), lots of sandpaper and few tools. I've done two western styled handles with just rasp, drill, epoxy and sandpaper. For western styled handles you'd better get yourself a disk or belt sender, and a drilling press, and some small files.
Overall the process of making new handle is very fun and rewarding. Hope you'll also like it. Be warned though… it's very addictive :)
On kitchenknifeforums.com you could find tons of different WIP (work in progress) threads about making new handles.