As always, everything depends on the nature of the attacker. How determined are they, what resources have they, are they targeting you specifically?
If your concern is regular, non-targeted malware, you should be OK if you keep a clean SD card with a custom recovery manager on it, and use that to flash the ROM. It's important that you use that card for nothing else, and never have it in the device unless you're booting from it.
This means you need a clean device at some point to create that clean SD card, and later to update the ROM.
If you are facing a targeted attack from a well resourced attacker, things get more serious, and you'll probably need to switch to a "burner phone" model, where you throw the phone in the trash every few days and buy a new one.