If the system must remain online, one tuning method is to first set KI and KD values to zero. Increase the KP until the output of the loop oscillates, then the Kp should be set to approximately half of that value for a "quarter amplitude decay" type response. Then increase KI until any offset is corrected in sufficient time for the process. However, too much KI will cause instability. Finally, increase KD, if required, until the loop is acceptably quick to reach its reference after a load disturbance. However, too much KD will cause excessive response and overshoot. A fast PID loop tuning usually overshoots slightly to reach the setpoint more quickly; however, some systems cannot accept overshoot, in which case an over-damped closed-loop system is required, which will require a KP setting significantly less than half that of the KP setting that was causing oscillation.
I'm not very good with the electronics side of this as I am more of a numerics nut, but I will help out at much as I can. How do you control the motors regularly without PID, what outputs do you send. How is the motor connected to the arduino. I know you mentioned this earlier but what are you using to measure position and what is the range of values you get from these.