The main purpose of the base resistor is to limit excessive current to the base. The BJT is a voltage controlled device and hence current is not the driving factor for switching. The base resistor needs to be large enough to prevent damage to the transistor, but should still allow sufficient current to ensure the transistor switches on and off as per the base voltages.
Not using a base resistor sometimes works, but it's a terrible practice and it's just asking for trouble. Relying on this mechanism runs the risk of burning out your I/O pin as well as damaging your transistor, so its recommended you use a base resistor. Without a resistor, you are placing 5V on a low impedance input (Base - Emitter), and asking the Atmega/Arduino pins to source a lot of current. Eventually, if not immediately, that is going to destroy your Atmega.
However, you do not need a base resistor if you operate the transistor in the common collector configuration sometimes called an emitter follower. This is because any current flowing through the emitter load cause the voltage on the emitter to rise to a point where it is 0.7V below the voltage on the base and prevent any further current flowing. This is a sort of negative feedback on the base current.
My thought is that your AVR controller should drive the relay directly just fine - provided that you do NOT switch the pins to input while the relay coil is energized.
Set both pins LO. Relay doesn't change state. Set one pin HI, wait a while, set that pin LO again. Relay changes to one state (or doesn't change, depending where it was originally).
When it's time to change the relay over, set the other pin HI, wait a while, set it LO again. Relay changes to the other state.
The only time there will be a transient is during the time when the pin is switching from one state to the other.
I am assuming that the protection diodes inside the chip will handle will handle the peak current that the pins are rated for - those diodes are a parasitic part of the output MOSFETs on the chip. They can't handle a significant amount of energy for any length of time but they should be able to handle the transients that you are going to get from turning the relay coil OFF until the other MOSFET has turned ON.
That is: the transient lasts only as long as it takes for the pin to change state from HI to LO or vice-versa.
I'm also assuming that you are driving one relay per pair of pins and that you aren't firing multiple relays at the same time.
If this is a low-energy design - that is: the entire circuit consumes only a few mA current, you may need to add a clamp to the + rail to stop it from rising.
Maybe.
Personally, I'd be putting a DSO on the supply rail and observing what happens as you fire the relay from one state to the other.
[Edit]
Note that the discussion above talks about whether it is safe to drive your relay directly from the controller pins. Now you need to find out if your controller will actually drive your relay. That is: will it supply enough voltage to properly switch your relay.
You say that the relay requires 20 mA @ 5V. That is a 250 Ohm load that is being driven by two output pins that are effectively in series. That is: the Rds_on of the pin that is held LO is in series with the Rds_on of the pin that is going HI. You need to find those Rds_on values for your controller under worst-case conditions and ensure that they allow sufficient voltage to the relay coil to switch properly.
Best Answer
The 40mA is an absolute maximum spec and not a place where the device is intended to operate. Even 20mA is a stretch, and TI doesn't specify what voltage you will have across the drain-source of the internal FET at that level. You can see the operating specs specify the output voltage at currents in the range of .4 to 5mA.
These devices are not intended to drive relays directly. It's very simple to use a 2N7000 type FET or a 2N3904 BJT hooked to the supervisor part to drive the coil. Always use a diode across the coil to prevent the inductive kick during turn-off from killing your switch device. (The diode should be rated for something like 1.5X the coil current, and for a voltage greater than the coil supply voltage.)
There's a nice diagram of a relay driver in the first post here: http://forum.allaboutcircuits.com/showthread.php?t=29461
You can ignore the text unless you find it interesting.