Quello che citi su timestamp e' riferito a mysql 4.0

A partire da 4.1 cambia il formato e si puo' scegliere quale timestamp incrementare e quindi non sara' piu' necessariamente il primo. Vedi anche l'annotazione alla pillola relativa a mysql 4.1

Per quanto riguarda il quesito iniziale si potrebbe sempre creare un id autoincrement e mantenere le chiavi attuali (due campi) in un indice UNIQUE...

ALTER TABLE table ADD UNIQUE `pippo` ( campo2 , campo3)