The resistivity of graphite is roughly three orders of magnitude as high as that of copper, so the skin depth for any frequency is going to be around 30 times that of copper. The efficiency of induction heating starts to decline rapidly when the workpiece diameter is smaller than four skin depths (due to eddy current cancellation within the workpiece). This suggests that the operating frequency for induction heating should be in the 10 MHz range or above. Since graphite is so much more resistive than copper, going below this frequency won't be disastrous for the electrical coil efficiency (the ratio of the reflected workpiece resistance to the total AC resistance of the coil + workpiece), but the amount of reactive power needed in the tank circuit will go drastically up. Personally I wouldn't go below a couple of MHz in this application.
This suggests that repurposing a metcal soldering station might not be such a bad idea afterall, if it provides enough power for you. I would calculate how much power you need given the thermal mass of graphite at the speed you want to move it, while pessimistically assuming that 50% of your RF power ends up in the workpiece.
For example, assuming you use a 3mm diameter rod and move it at 5mm/sec, you need to heat up pi * ((3 mm)/2)^2 * 5 mm = 35 mm^3 ~ 80 mg of graphite a second. The specific heat of graphite is around 0.72 J/gK, so if you want to raise the temperature by 300 K then you will need 0.72 J/gK * 300 K * 0.08 g/s = 17 J/s = 17 W of power delivered to the graphite. This suggests that a common 50 W metcal station would have enough power, as long as you can get the impedance matching reasonably good. If you need more power, you could use a higher powered RF amplifier to drive it, like those used by radio amateurs.
If you want to go in this direction, I would suggest repeating my calculations as they were done quickly and may contain errors.