Tried getting one in Bispebjerg Kommun and they refused me. I had a smartphone. I told them that a security update bricked my phone's security. I was told to simply buy a new phone.

First off, that's just wrong of them. I don't know, but I think you could file a complaint with indenrigsministeriet, and if they tell you to take a hike then Folketingets Ombudsmand.

But more importantly, you can circumvent the local yahoos and order it online instead. https://www.mitid.dk/en-gb/get-started-with-mitid/how-to-use-mitid/mitid-code-display/#order you will need a valid passport though.