Perche' non metti una validation sullo slug che non consenta di utilizzare uno gia' preso? Cosi' puoi usare lo stesso titolo ma sei obbligato a far si' che il nuovo slug sia diverso da quelli gia' presi. In questo modo puoi cambiare una parola etc. nello slug soltanto.

Altrimenti non mi viene in mente un metodo senza includere un id, una data, etc., se vuoi che lo slug venga generato automaticamente. Come dice partime cmq ti conviene usare - invece che _.

Per quanto riguarda il SEO 'sminchiato' a causa dell'id etc, dove l'hai sentita?