There is not a concrete answer to this question since new host functions are changes in the client, which cannot be upgraded on-chain.
There will be three main steps needed to get a new host function onto the Polkadot network:
Agreement about the host function specification.
Adding a new host function is a big change, and importantly is something that must be supported for all time once it has been added, even if it becomes deprecated, since it would be required to sync old blocks on a chain that used it. Thus the most important part of the process is to clearly define what the host function should do.
The best place for this is an issue in Substrate / Polkadot or in the PSP repository: https://github.com/w3f/PSPs
Implementation of the host function.
After an agreement is made, all Polkadot clients will need to update their codebase to support it. This is an important step to call out because there may be different client implementations in the future, and before a node can use this new host function, all of the implementations will need to be updated. This is also a point where developers who may really be against some idea would choose not to implement this function, and that could of course cause problems on its own.
The network needs to update their client.
Finally, once the host function is implemented for all the different Polkadot client implementations, then all of the node operators will need to update their software. Again, this is an opportunity where node operators who are really against some idea may choose not to upgrade their client in protest.
Hopefully this also paints a picture about what on-chain governance and on-chain runtime really simplifies the concrete way to do upgrades. Unfortunately, this is not something that can be safely done for blockchain clients.
In most cases, steps 2 and 3 are not usually a contentious problem, and usually the community works together to implement new features, however there have been examples in the past (like Bitcoin Cash and ETH Classic) which has shown this is not always the case.