You could probably design your icon as a selector that has two states: updates_available, or normal. You would have to create the custom state and override the method in the launcher activity that handles setting the icon. Then, you would have to write a persistent service that periodically checks for updates and broadcasts to the launcher.... but this would require you build your own launcher.. which I'm assuming is not an option.
But there are two ways to do this which will yield a similar result:
1: Create a 1x1 widget which is simply an image view that launches your activity on press. This widget will accept broadcasts from your update checking service and change its image accordingly. This is very similar to the way you would "want" to do it mentioned above.
2: Have your application add a shortcut as described here:
How to change an application icon programmatically in Android?