I'm slightly concerned that the decoupling caps
That looks like it might work. The only problem might be when the arduino want's to turn off and it will not be able to hold the output high long enough to be off.
Just looked at your schematic; never come across single coil latching relays before, I've only got double-coil ones. Interesting. A bit confused about C1, though; why is it there? Doesn't it stop the current flowing before the relay's even had a chance to think about moving?