1) Open iPhone Explorer and navigate into the app’s folder, located in /Apps/appname.app/appname.app.app ( appname is the name of the app you want to change and devicename is the name of your device).
2) Within that folder, find the png file that is the icon, named something like [removed] for an iPhone 4, or Icon.png for iPhone 3GS and earlier.
3) Back it up and replace it with your own icon. Make sure the icon is in PNG format and is 114×114 pixels for the iPhone 4, 57×57 for the iPhone 3GS and earlier.
4) Reboot your iDevice.
You should now see the old icon replaced with your new one.
However, this trick works only with 3rd party apps, this means that you are stuck with the icons for apps that come with your iPhone