The only challenge I can see is that it must be possible to override this rule in the case where you have fewer territories than income. (Although this would be incredibly rare, and the game would work just as well if you weren't allowed to deploy extra armies, instead.)
I'm not sure whether it has been suggested before. I haven't read all posts in the thread. Sorry if it does.
We compare two numbers. The first is your set limit per territory. The second one is total number of armies / total number of territories owned. Whichever higher will be the limit that turn. The formula will be:
=max(limit per territory, total number of armies / territories)
The advantages are we can keep it consistent and don't need to touch the rule (i.e. all armies must be deployed).
Edited 9/18/2015 14:39:06