I was thinking about this kind of thing. Another idea might be to introduce artificial latency and gradually increase it over time? Maybe dial up rate-limiting? I'm not really sure if this is a better or worse idea, though.
There'd be nothing that indicates "The API is going to get shut down in a month and I need to move off of it ASAP!". Random, intermittent API failures would lead you to go check the API status out, and in the process you'd find out "oh, this API is going away".
Edit: On the point of rate limiting, I think the problem with it is that it'll affect everyone using the API all the time, not just during the brownout period. It effectively shuts the API down for everyone still using it (if the rate limit is too low, and if it isn't, then it won't be noticed by low-use consumers).