To generate any kind of non-square waves on Arduino, you would need to output analog values
Not necessarily, you could use the arduino to charge and discharge a capacitor (through a resistor) through one half of a H-bridge or even from an output pin directly. You could either swap directions after a fixed time or when the capacitor voltage had reached a certain level. This would not be a true saw waveform as stated above but would be close. To get a true saw then you need to charge at a constant current. This is easily done by using an op amp and having a capacitor as the negative feedback path. You could then feed the positive input straight from the arduino pin.
However I would still use a NE555.
What exactly is the purpose of this saw tooth? Is it to act as a threshold for generating PWM? That is the normal use but you can generate PWM directly from the Arduino.