Well, there are two options here:
First, you can create a custom Walker to use PHP to add that rel attribute to each category. The benefits to this method is you will be guaranteed to have that attribute added each and every time since it's PHP doing the work. The downside is that you'll need to know how to write a custom Walker, and more importantly you'll need to know how to program in PHP.
Let me know which way you'd like to go and I can offer assistance to both methods.