When opportunity status changes automatically (Ex. When creating the Quote based on the opportunity, the opportunity status changes to "Quote") workflow does not trigger this change. Any idea how to handle this other than using a scheduled workflow?

Well the answer is a Schedule Workflow or Script. Please explained why these options are not suitable for you context. One other way would be to trigger from the Quote Create where Created From is Opportunity. Need to know more context of what you are doing.