That's a bit misleading. The US Constitution doesn't have any rights in it either. The Bill of Rights are amendments to the US Constitution, which demonstrates that US government can change their constitution.
Well, amendments are part of the Constitution.
More importantly, the procedure for making those amendments is itself spelled out in the Constitution, which gives a certain amount of protection from whims.
Secondly, the UK Constitution is considered to consist of two fundamental concepts.
1) Parliamentary supremacy
2) Rule of law
Okay, stop right there. A "constitution" is a document or set of documents. Already, if you're saying that a UK constitution is a set of "concepts," you've more or less proven my point about the absence of "unconstitutional" having any real meaning under UK law.
The other problem, of course, is that "rule of law" is somewhat meaningless when the lawmakers themselves are not bound by that same rule -- which under the UK system, they are not. That's been a traditional problem of the various banana republic governments (and for that matter, the authoritarian
L'etat, c'est moi divine right emperors), which is more or less the system against which the idea of "constitution" was created.
The UK
does have a constitution in the stronger sense that I've described, but it's not clear what it is or what powers it actually possesses. In particular, the Magna Carta explicitly destroyed the idea of a limitless royal executive of the sort Louis XIV would later embody, precisely because there are/were things that the king could not do. UK court case have similarly held that there are, in fact, limits on Parliamentary supremacy (in particular, look at the "mischief rule, and more importantly the doctrine of "implied repeal" -- while Parliament could in theory overturn the Bill of Rights 1689, it could not do so implicitly by merely passing a law that conflicted with it.) In this sense, Parliamentary supremacy
has been reduced (a judge could overturn a recent law as being incompatible with the Magna Carta or the Bill of Rights 1689, which is a pretty good description of "unconstutional.")
But this is a relatively new legal development, and there's no definitive statement about which laws cannot be repealed by implication and which laws can, or the limits to how much of a law can be overturned on this basis, or even what the procedure is (which judges get to make that decision).....