При настройке уведомления просто установите в поле .when значение Integer.MIN или Integer.MAX, чтобы соответственно иметь уведомление слева или справа.
Значки сортируются по этому полю во всех версиях Android, вплоть до ICS.
В JB (4.1) вам нужно установить приоритет уведомления, чтобы получить его слева или справа:
messages.priority = PRIORITY_MIN для правой стороны
tification.priority = PRIORITY_MAX для левой стороны
РЕДАКТИРОВАТЬ: если на планшетах вы используете Notification.FLAG_FOREGROUND_SERVICE или startForeground, значок будет располагаться вправо, и все, что я пытался переместить влево, не работало (протестировано на ICS).