True circumcision (the removal of the foreskin) is likely an Islamic introduction in Southeast Asia. There was a similar practice in the Philippines and in many other parts of the Austronesian world, but it's generally supercision and not circumcision. The foreskin isn't removed entirely, you just make a cut in it. We know there was a meaningful difference between circumcision and supercision for Early Modern Filipinos because they differentiated between the two practices (in the Visayas, supercision was called tuli and circumcision magislam, from the religion).

Supercision is still practiced in non-Abrahamic parts of Southeast Asia, usually as an initiation ritual (whether public or private). In non-Islamic parts of the Indonesian peninsula of South Sulawesi, for example, a boy who has reached puberty decides when he is ready for a supercision. He goes to the riverbank accompanied only by an experienced old man, who carries out the operation and uses the cold water to reduce the pain. After this is done, the boy can no longer walk around naked like little boys do; he is a man now.

Some other Southeast Asian cultures practiced subincision, in which the penis is cut lengthwise. This was primarily common in eastern Indonesia, so perhaps it reflects influence from New Guinea, where the practice was widespread? I don't think any research has been done on this, though.

Many Southeast Asian men modified their genitalia prior to the introduction of Abrahamic religions in ways other than supercision or circumcision: the insertion of objects into the penis. The most dramatic is the surgery of palang insertion, still practiced until recently in non-Islamic areas of Borneo and Sulawesi and in the precolonial Philippines as well. The palang is a pin (most often metal, though historically bone and bamboo could be used) driven through the glans of the penis. Once the wearer recovers from the operation, he could freely attach small objects at either end.

NSFW image of a penis with palang but without additional ornamentation.

That's a fairly plain palang. Here are some fancier ones (SFW) from Tom Harrison's 1964 article "The 'Palang,' its History and Proto-History in West Borneo and the Philippines."

The Venetian explorer Antonio Pigafetta, who accompanied Magellan on his voyage around the world, is the first European whose account of palang has survived. He is absolutely bewildered:

The males, large and small, have their penis pierced from one side to the other near the head with a gold or tin bolt as large as a goose quill. In both ends of the same bolt some have what resembles a spur, with points upon the ends; others are like the head of a cart nail. I very often asked many, both old and young, to see their penis, because I could not credit it. In the middle of the bolt is a hole, through which they urinate.....

Virtually everyone who wore palang, from Pigafetta's informants to modern Southeast Asians, said that the point was the sexual pleasure of the woman. Here's what one informant told an anthropologist in 1961:

At one time a number of girls slept together, naked. As they slept, a dog came and saw them all naked. The dog licked the parts of one of them which she [the girl] felt most sensitively. She rose up to see the dog standing nearby. She drove it away. Shortly afterwards the dog came again, the same girl asked it to lick her again and again. She found this so enjoyable, she did not tell it to any of her friends.

While she was sitting alone in the house next morning, the same dog came again. She dragged its head to lick her. The dog refused. A day later, as she slept at day time, the same dog came in. She dragged its head to lick her again. The dog turned its head away. As a result, she began to think of the sensitive feeling, while being licked by the dog two days before.

As she thought over the matter seriously, she went out of the house to collect leaf, which she rolled and put very carefully into her. When she had done this, she felt the effect.

She did this daily in the loft of the house. When someone called her to ask what she was doing, she simply said she was busy. One day when she put the leaf in, two girls peeped through at her, to see what she was up to. They then asked her why she was doing this thing. She shamefully told them that, by doing so, she got a very sensitive feeling. She also explained she must do it regularly, everyday. The two girls asked her more about the actual feeling. She assured them it was wonderful, beyond description.

On hearing this the two girls each put a leaf in for themselves. As they felt the effect, they agreed. From that day on, these three girls habitually put in leaf.

After some years in the habit of doing this, they fell in love. One night, as a young man was having intercourse with one of them, the girl told the young man that his action was no better than being driven with a leaf!

The complaint of the girl upset the young man. He said he had treated his other girl friends in the same way, in the past, without complaint. The young man was thoroughly ashamed of the girl's words. In the morning he thought it over carefully. Finally he decided the only way to please her was to place something at the tip of his own organ. He went into the nearby forest, in due course, and made a tiny hole, to pierce a rod through it!

After he had fixed this at the tip, he had further intercourse with her. Now she said she was very satisfied indeed. It is due to this that the palang ever came to being among us Kayans.

The Spaniards were absolutely horrified by palang. The Boxer Codex, a 1590s Spanish manuscript about the Philippines and its peoples, says (emphasis mine):

Finally, in the sin of the flesh, they are used to a thing which is the newest and never hitherto seen nor heard -- which seems to be the guide to vice and bestiality that they have in this particular... [a description of palang follows] Thus they have access with the women, with whom they remain for a day or a night in the way dogs do a similar act, after completing which they remain immensely satisfied, specially the women..... The Spaniards have had special care after coming among these people to abolish this abominable and bestial custom among the natives, punishing with beatings those who wear them..... [This is] a custom invented by the devil so that men may offend more with this vice our Lord God.

Twenty years later, Spanish lawyer and historian Antonio de Morga remarks triumphantly:

From childhood, they [the Filipinos] become accustomed to one way [of intercourse]: the males cleverly make a hole in their virile member at the end, and they insert into it a small head..... These devices are called sagras; and there are very few [left], because now that they are becoming Christians, care is taken to get rid of [such] and not to let them use them, so that [this practice] has been remedied to a great extent.

Islam was similarly effective at ending the practice of palang, but we know much less about the process.

The palang requires a very painful operation and half an year of sexual abstinence. Many Southeast Asians preferred to simply insert small balls under the skin of the penis. Unlike the palang, most common in commercially underdeveloped areas of Southeast Asia, penile balls were everywhere, from Myanmar and Thailand to Java and Sulawesi. Indeed, the fifteenth-century Javanese temple complex of Candi Sukuh features statues of men grasping their penis with balls inserted and lingam statues in the shape of a ball-inserted penis.

This, too, ended in Indonesia with the coming of Islam.

There is more research to be done on penile inserts in Early Modern Southeast Asia. To my knowledge, most of the useful information is still to be found in Brown, Edwards, and Moore's 1988 The penis Inserts of Southeast Asia: An Annotated Bibliography with an Overview and Comparative Perspectives, which isn't very accessible. Reid's first volume of Southeast Asia in the Age of Commerce also contains a good overview of the practice in pages 148-150.