Change app icon permanently
You have to change the icon every time it updates because, as you have correctly pointed out, the Package is replaced and therefore your icon is overwritten by the original one. 

To make your life easier, you might want to take a look at CandyBar, it makes that job easier :)