I'm pretty sure when you configure certificate pinning you can also specify an expiry date. Party A would just adjust the expiry time to match their cert expiry and both parties are happy.
Apart from that, how does B get the new cert in time from A and how to guarantee the new cert is effectively for the same party A (and not some mitm)?
I'm not sure how the "hey, I'll switch to this cert soon" bit should be done, though.
(It's also kind of worthless. Since people normally change their secret because they have some reason to believe it's compromised, whoever has the old key can also create the same certificate. In other words, it's only useful on the use cases where pinning already fails...)
So you could have a workflow like:
1.) Party A generates the initial certificate and passes it offline securely to Party B
2.) Party B stores Party A's certificate in their java trust store
3.) Party A creates an HTTPS endpoint where they host a copy of their current certificate and their certificate for the next time period: https://www.PartyA.com/nextcert.crt
4.) Party B upon connecting for the first time validates that the certificate on the HTTPS site is the one provided in step 1
5.) Party B retrieves nextcert.crt from the URI in step 3 and places it in their java trust store
6.) 30 days before expiration Party A generates a new LE certificate and places it at the URI in step 3
7.) 7 days before expiration Party A sets their certificate to be the one at /nextcert.crt
Day 1 - Party A generates Cert1 and provides it to Party B, secures the domain with it (https://www.PartyA.com/) and places it at /nextcert.crt
Day 2 - Party B retrieves /nextcert.crt (it's still Cert1)
...
Day 60 - Party A generates Cert2, and places it at /nextcert.crt
Day 61 - Party B retrieves /nextcert.crt (it's Cert2), and places it in their store. Now they have two valid certs for Party A (Cert1 and Cert2).
...
Day 83 - Party A secures their domain (https://www.PartyA.com/) with Cert2 (/nextcert.crt has already been pointing to Cert2 since Day 60 and continues to do so)
Day 90 - Cert1 expires. Party B only has 1 valid cert in their store now.
...
Day 120 - Party A generates Cert3, and places it at /nextcert.crt
Day 122 - Party B retrieves /nextcert.crt (it's Cert3), and places it in their store. Now they have two valid certs for Party A (Cert2 and Cert3)
...
Day 143 - Party A secures their domain (https://www.PartyA.com/) with Cert3 (/nextcert.crt has already been pointing to Cert3 since Day 120 and continues to do so)
Day 150 - Cert 2 expires. Party B only has 1 valid cert in their store now.
Then just continue this process in a loop. This allows for the two properties requested. Party B is able to validate Party A (because an initial cert was provided offline), and that the next cert is actually from Party A (as the transfer of the new certificate is done via a secure channel using existing certificates)
A similar thing happens sometimes when new GPG keys are generated. Google for "GPG transition statement" for how that works (it's effectively the same process).