You should be able to do this with Notification and the NotificationManager. However getting a guaranteed way to know when your application is not running is the hard part.
You can get the basic functionality of what you are desiring by doing something like:
Notification notification = new Notification(R.drawable.your_app_icon, R.string.name_of_your_app, System.currentTimeMillis());
notification.flags |= Notification.FLAG_NO_CLEAR | Notification.FLAG_ONGOING_EVENT;
NotificationManager notifier = (NotificationManager)context.getSystemService(Context.NOTIFICATION_SERVICE);
notifier.notify(1, notification);
This code must be somewhere where you are sure will get fired when your application starts. Possibly in your application's custom Application Object's onCreate() method.
However after that things are tricky. The killing of the application can happen at anytime. So you can try to put something in the onTerminate() of the Application class too, but it's not guaranteed to be called.
((NotificationManager)context.getSystemService(Context.NOTIFICATION_SERVICE)).cancel(1);
will be what is needed to remove the icon.