Como converter strings de data em timestamp sem saber o formato de data

Você precisa definir seu estilo de data para "ISO, DMY". Ele é definido como "ISO, MDY" por padrão e faria com que seu exemplo falhasse:

> show datestyle;

 DateStyle 
-----------
 ISO, MDY
(1 row)

> select '28-Sep-13'::date;
    date    
------------
 2013-09-28
(1 row)

> select '28/09/2013'::date;
ERROR:  date/time field value out of range: "28/09/2013"
LINE 1: select '28/09/2013'::date;
               ^
HINT:  Perhaps you need a different "datestyle" setting.

> set datestyle = 'ISO, DMY';
SET

> select '28-Sep-13'::date;
    date    
------------
 2013-09-28
(1 row)

> select '28/09/2013'::date;
    date    
------------
 2013-09-28
(1 row)

(exemplos feitos no PostgreSQL 9.1, mas a configuração DateStyle e o comportamento associado são antigos, então deve funcionar bem)