"Put" and "but" both end in the same letters, so why don't they rhyme? Did they start out with the same sound, and then one of them changed? Or did they start out with different sounds, and just got spelled with the same letter because there weren't enough vowel letters to represent all of the vowel sounds in English?
English is over a thousand years old, and has been through so many changes in the meantime that even very competent speakers struggle with English as it was written a few hundred years ago, and that of a few hundred more is so different as to essentially be a different language entirely.
This has left us with a great many inconsistencies, and the fact that English borrows from different languages, at different times, with different degrees of Anglicisation, leaves us with many more (though not in this case).
Some of the reasons for particular cases are hard or impossible to track, and some are open to reasonable conjecture, while others we can make more reliable statements about.
The word put was in Middle English found as putten, puten, poten and a separate word pytan. It's believed it came from a late Old English word putung.
The word but comes from Middle English buten, boute, bouten, from Old English butan.
In Middle English, these words, along with many others with a u in them would have had a /u/ sound (like a French ou as in vous). So, they would have rhymed as their spelling suggests, though neither would sound quite like they do in most modern accents.
As you have probably noticed, accents differ greatly from each other in how they pronounce many vowels. Accents differ not just with space (which we can easily realise by listening to how different people pronounce the same word differently), but also through time, which leaves some record today (listen to recordings of people from several decades ago, especially working class people, and you may find their accent doesn't match how people of the same area talk), and also helps explain how the regional differences arose.
In the early Modern English period, the /u/ sound changed, to a /ʊ/ sound (like the oo in foot).
Then it changed to first a /ɤ/ sound, which then changed further to a /ʌ/ (the sound but has today) sound in some, but not all of the words. Generally whether it changed or not depended on the surrounding consonants, but this was inconsistent so even one-time homophones put and putt now have a different vowel.
So while but, cut, put, putt, fun, full, sugar once all had the same vowel, a change in vowel happening for some, but not all, of them split them apart. This also affected some oo words that had previously shifted sound to the same /ʊ/ sound (hence blood rhyming with dud rather than with good).
This happened in different areas at different times, and there are still accents where but and cut rhyme with put. This is also one of the reasons we've clues to what happened, since people in the mid 17th Century were noticing how the words rhymed in some accents, but not in others. (The split here is called "the foot and strut split" because those accents rhyme the words foot and strut, while others do not).
Now, while you'll often hear that spelling was inconsistent in English until relatively recently, this is only true up to a point; certainly it was a lot less firmly set than today, but there were certainly conventions followed (even if they differed by region) so it wasn't a phonetic free-for-all either.
Between this, and the lack of any clear way to differentiate the too sounds (all the more so earlier in the change), we still have the same u letter used to spell them, even though they now have different sounds.
"Put" and "but" rhymed historically if you go far enough back; this is why they are spelled similarly. In some modern accents, they still rhyme. So in this sense, the spelling is not arbitrary; nor is it particularly illogical (although it is somewhat inconvenient for people who pronounce these words differently).
As you say, in standard British and American dialects they don't rhyme. What is called a "sound split" occurred: what was originally the same sound developed different pronunciations in different words. These kind of splits often follow regular rules, based on the surrounding sounds in a word, but sometimes the splits are incomplete or have exceptions.
The origin of the split is the unrounding of /ʊ/ in Early Modern English, resulting in the phoneme /ʌ/. In general (though with some exceptions), unrounding to /ʌ/ did not occur if /ʊ/ was preceded by a labial consonant (e.g., /p/, /f/, /b/) and followed by /l/, /ʃ/, or /tʃ/, leaving the modern /ʊ/. Because of the inconsistency of the split, the words put and putt became a minimal pair, distinguished as /pʊt/ and /pʌt/. The first clear description of the split dates from 1644.
This passage includes a description of the general pattern of the split. One interesting fact is that /m/, although also a labial consonant phonetically, never prevented unrounding (hence mull, mullet and mush don't rhyme with pull, bull, full; pullet, bullet; and push, bush). For words with the sequence "ul" specifically, you can look at this related question to see a list of how these words are pronounced and a more precise description of the rules in modern English: Do “hull” and “full” rhyme?— rules for “short U” sounds before L.
However, the pronunciation of put as /pʊt/ is an exception not explained by the general rule. It's probably relevant that put does start with the labial consonant /p/, which seems to have affected the following vowel in the regular cases as well.
There are other exceptions that show irregular retention of rounding, such as pudding and pussy (compare budding, fussy), and the word cushion (where there is a following /ʃ/ but not a preceding labial consonant).
On the other hand, there are some words spelled with "u" preceded by p/b/f and followed by l that have unrounded /ʌ/ instead of /ʊ/ in standard British and American English, such as pulp, pulse, pulverize/pulverise, bulk, and bulge. (In other varieties of English, one or more of these words may be pronounced with /ʊ/. For example, with regard to "bulge" see the second pronunciation listed at merriam-webster.com and this question on English Language Learners Stack Exchange.)
To augment the answers given already (specifically sumelic's answer), you have to take account of the fact that for most of the history of the English language most people were illiterate. Which means if the pronunciation of a word (like "knight") for example, gradually changes over time, the original spelling isn't in the back of the speakers mind pulling them to an earlier pronunciation. Once a pronunciation changes, that is essentially now cemented once it passes across a generational line and no one remembers how it used to sound.
This is by no means the only reason English orthography doesn't match pronunciation, but in this case it is.
Little side note :the opposite of this is called a "spelling pronunciation", when the pronunciation of a word by a largely literate population actually changes to reflect the spelling (in some cases an older pronunciation but in others a completely new pronunciation) e.g. pronouncing a C in Arctic that was never pronounced.
The difference goes back more than a thousand years, so we would have to ask why these words were pronounced differently even in their earliest manifestations. I assume that the pronunciation was originally connected to the meaning. "Put," for example, is related to "push," so perhaps the forcefulness of the action was felt to require the somewhat "longer" sound of the vowel. This is conjecture, but it fits with the concept that many words began as verbal representations of real things.
Another possibility: These words (like many others) were connected to words in other languages. If an antecedent word in another language carried a particular pronunciation (for whatever reason), then that pronunciation might be carried over into the English version. (This doesn't always happen, but it's fairly common.)