How can you express this without state? Or more generally, any “random_password”, “random_choice” etc, or even anything that is a “write only” property
You can’t. So this is dead in the water.
Do you in practice really use random names? In my experience, I'd just use a loop vm01...vm10 for the names and the passwords aren't needed to identify an instance after the deployment so here randomness isn't an issue.
Random passwords, write-only attributes (like database master passwords) are the most common.
How do you express “create a DB with this strong password, then put it in a s3 object”, then later “actually put it in SSM rather than s3”?
With Bicep, we mostly deploy only the initial state and then we either re-deploy the whole thing or, if this isn't possible due to the interruptions this causes, add migration scripts in an imperative language (az cli/ pwsh). Which is admittedly the much less elegant approach.