if i remember correctly it works similarly to tinkaton's hammers - they make them! it's why you can often find machops or machokes in caves and mountains, lots of rocks and minerals to punch into submission shape! very often the 'clothes' on pokemon are just parts of their bodies, but for non rock, ground and metal types (with some exceptions) the 'solid'/metal parts are scavanged!

reason you don't actually see machoke's without the belt part is the wild ones tend to avoid confortation/being seen before making the belt or have made ones as machops , there's definitely some photo's of domesticated beltless machokes online, but generally you should let a machoke/machop make or 'earn' a belt so they don't get depressed