Posso sostituire la frase 'Mi dispiace, ma adesso devo andare' con 'Mi chiedo scusa, ma devo partire'?
"Mi chiedo scusa ma..." is plainly wrong. It would be like saying, in English, "Forgive you, but I have to go".
Now, between "Mi dispiace, ma...." and "Ti chiedo scusa, ma...": they are basically the same. In the everyday use I don't see much of a difference. Probably the second is a slightly more polite form, but it could be a matter of personal taste. In an informal conversation, say with a friend of yours, I would prefer "Mi spiace, ma...". If you want to be perceived as truly sorry for what you are about to do, you could say "Mi spiace, ma ora devo PROPRIO andare".
There is also a difference between "andare" and "partire". You use the first one, for instance, when you are talking with a person but you become aware it's late and you need to go and leave the person there. In this situation I would not use "partire", it would sound a little bit strange even if the meaning would be understoood perfectly. You use "partire" in the same situation if you need, for instance, to take a flight or a train. Or if you need to start for a planned trip. So, in the first case, leaving is something slightly more unexpected. In the second case, you already knew you had to leave at a certain time.