EXATAMENTE por isso que você vai salvar o slug e ele deverá ser unique...
Man, não tem dificuldade nenhuma isso que você quer fazer, principalmente com o quê você já tem pronto. A questão é isso que você acabou de dizer, que não é um profissional de desenvolvimento e suponho também que não fez o quê está pronto agora, certo?
Enfim mais mastigado que meu trident diário:
sua tabela terá uma nova coluna que é o slug em si;
na inserção da notícia você irá salvar esse slug e capturar eventuais erros de duplicate key e ver como tratar;
no mod_rewrite vai retirar o ID;
na busca vai pesquisar pelo slug ao invés do ID.