I would use a single transistor rated at minimum 1A continuous (a MOSFET by choice), and have both LEDs switched in parallel with their own resistor. By having them in series as in your second schematic you are limiting the input voltage to a minimum of 2×Vf which could be as high as 5.2V, and thus more than your power source can provide.
simulate this circuit – Schematic created using CircuitLab
This gives the same result as your first circuit, but only uses one transistor for the switching. You can add more LED+Resistor pairs in parallel as you like as long as the total current is below that which the chosen MOSFET can handle.
You should rate the MOSFET to handle the maximum continuous current, not the pulse current, in case the output of the Arduino should be set continuously HIGH instead of sending PWM.
You should also note that the pulse current of an LED is usually rated at 1% duty cycle.
Also note that as the voltage of your power source drops, so will the voltage across the resistors, and thus the current flowing through them (and your LEDs) making the LEDs dim. It may be beneficial to first pass your battery power through a high-efficiency 3.3V switch-mode regulator to keep the voltage stable whilst wasting the minimum amount of power in the regulation.