Routing, not rewriting is definitely the way to go here.
We usually build objects with two unique keys. First is the good old fasioned immutable primary key -- typically an integer or a guid depending on requirements. Second ID is a mutable, human editable one for the URL slug. Load things on the public facing side by url slug, problem solved.