AVR single coil latching relay
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.