Hello,
There is no way to do this without breaking the failover, but there should be no downtime involved.
Just apply the new license to both (after applying to the first you will get the message stating that failover has been disabled). You should then see failover state on the secondary device as "Secondary (pseudo-standby)".
Go back to the primary and activate failover again:
ciscofirewall(config)#failover
You should then see the message stating config is being replicated to secondary device.
Let me know if you need any further info.
Chris