This is a translation of a literary phrase in English (off Shakespeare if I'm not mistaken), and it does sound good in Norwegian to say it like that, with uten. If you want the same sentence without uten you would have to find some expression, like En rose som ikke har rosens navn.
You could rewrite it into "En rose med et annet navn", "En rose som heter noe annet enn rose", "En rose med et helt annet navn enn rose", and what is closest to a literal translation: "En rose med et hvilket som helst annet navn",
"A rose by any other name . . . " is indeed from Shakespeare. The quote finishes, " . . . would smell as sweet." It is from Romeo and Juliet. He is working to convince her that it does not matter that each of them bears the surname of the other's family's enemies. Basically, he is telling her, "You are the one I love, and your family name does not change that. I can call you beloved or enemy, either way you are still yourself ("and precious to me" is implied here).