In your comment, you linked to an official source that (rather understatedly) answers your question:
To save the taxpayer money, the newly designed passports will be introduced in a phased approach.
After the UK leaves the EU, burgundy passports will continue to be issued but with no reference to the European Union.
New blue and gold passports will be issued from October 2019, when the new passport contract begins, to those renewing or applying for a new passport.
There is no need for British passport holders to do anything ahead of their current passport renewal date.
(Emphasis added.)
Of course, the first paragraph is somewhat disingenuous:
After Brexit, the UK travel document will no longer be required to conform to EU standards. So in a move to symbolise our national identity, the cover will be changing from the standard EU burgundy colour to a blue and gold design.
This implies falsely that the burgundy cover was required by EU standards; in fact, it is just a suggestion, and the UK could have gone back to a previous passport color, or indeed any passport color, without leaving the EU, just as Croatia has retained blue passports after joining it.
The implications for your question:
I've read/heard that when we leave the EU, also destined for March 2019, this will result in passports needing to be replaced with non-EU ones.
That is incorrect. Existing passports will remain valid until they expire.
Has any advice been published on when/at what cost this replacement will happen?
No, because there will be no such required replacement. People who want to pay the fee to renew their passports early will presumably be able to do that.
Some scenarios I've thought about;
1. If I renew now, the new one will stay valid until its expiration; new "British" passports would be issued only as existing "EU" passports expire.
This is what will happen.
- I renew now, and in 5 months get issued a new "British" passport, without extra charge.
That is wishful thinking, but fortunately it won't be necessary to get a new passport.
- I renew now, and in 5 months my "EU" passport dies, and I have to pay for the new "UK" passport.
No. The EU doesn't issue passports. An "EU passport" is a national passport issued to an EU citizen by an EU member state. When the UK ceases to be an EU member state, UK passports issued to British citizens will cease to be EU passports, notwithstanding any references they may contain to the European Union. But they will continue to be UK passports, and valid.
- I don't renew now, and wait for the new "UK" passports to be announced and get one then.
They've already been announced, as noted above, but you can certainly wait until October 2019 before getting your new passport, if your travel plans allow. In determining whether your travel plans allow, don't forget that some countries require extra validity beyond the end of your visit.