I can think of a few options:
1. Make day_of_week return a cardinal value in this case by passing :monday as argument to Date.day_of_week
2. Same as above but make the starting day_of_week an option, so you could return starting_day_of_week as part of your options (and you will probably default to :monday on all of them anyway)
However, I believe the issue above is not specific to day_of_week? If it is not:
3. Change all callbacks functions in strftime to optionally receive a calendar. We could check the function arity and dispatch accordingly
4. Same as above but you do it in CLDR.strftime, which you add, and wrap all functions to receive the Calendar
My preference, for simplicity, would be 1 or 2, probably 2 for backwards compatibility.