The newest trends in body modification seem to be pocketing, flesh stapling, flesh plating, flesh coils, implants (transdermal, beading and 3D art), surface weaving and chain piercing. Currently none of the practices are very well known even among seasoned body piercers, and many who do know what they are won't perform them anyway. One leading studio in the field of unusual body mods is the Finnish Mad Max Tattoo which is (according to them) the only studio doing implants and related procedures in Finland. One of their artists has even invented new piercing methods and types of jewelry. Most of these methods are relatively new, appearing only recently (in the past couple years or so) on the body piercing scene, and are becoming popular among people who wish to stand out or have something of which many people have never even heard.
All of these body mods are all based on the same principle as "traditional" body piercing: if you insert a non-organic substance (most commonly surgical grade stainless steel, titanium, Teflon or silicone) under your skin and keep nasty germs away from it, your skin will heal around it and accept the substance as a new part of the body. (Sometimes the body doesn't want to accept the piercing and it may be rejected, or slowly pushed through the outer layers of the skin until the jewelry just falls out. Most traditional piercings are punched right through a protruding part of flesh, like an earlobe, lip or nose: because these piercings pass through the entire epidermis, rejection is very uncommon; however surface piercings like the eyebrow or navel punch through a few layers of skin, tunnel sideways for a little while, and then punch back out the top. Because of the nature of surface piercings, rejection is much more common and usually a definite after long enough.) A very sharp hollow needle is always used for a good piercing of any type, especially more extreme methods such as those on which I'm about to expound; piercing guns (you see 'em at the mall) are impossible to sterilize, unprecise, and rip a hole in your flesh with a dull piece of metal. Bad.
Bit of an Overview:
Pocketing, stapling and plating are something like an inverse surface piercing: normally, the ends of the jewelry are outside the body and the middle is what passes through flesh; with these kinds of piercing the ends of the jewelry are buried under the flesh and the middle is exposed for all to gawk at. Implants come in three varieties (so far): transdermal, 3D art and beading. Transdermal implants are what getting spikes embedded into your head would be; 3D art implants are like putting a shaped piece of metal or plastic under your skin so it's all bumpy-like; and beading is similar to 3D art implants except a small bead is placed under the skin. Weaving is surface piercing to the max: take a couple deep surface piercings and connect them all with one long strand of plastic. Chain piercing is very similar to traditional piercing, except a small chain is used as jewelry instead of a solid ring or barbell.
The pocketing procedure involves making two incisions (normally with a piercing needle) facing away from each other deep into the flesh and suspending a solid piece of metal between the two, with each end in each "pocket." This may be done pretty much anywhere on the body, but a good layer of fat helps the piercer do zir job and will probably not hurt as much. Popular locations for pocketings are the forearms, collarbone area and back, though I suppose if deep surface piercings and implants are possible on the forehead, pocketing could be too...
The stapling procedure (invented by Samppa, Finnish piercer extraordinaire) uses the same idea, but the incisions are deep and narrow and face away from each other. One end of a staple-shaped piece of metal wire is first hooked into one incision and the other end is carefully (and painfully) hooked into the other incision. Again, possible pretty much anywhere on the body but a layer of fat is good. Popular locations are anywhere on the arms, or the collarbone and neck area.
The plating procedure is very similar to the stapling procedure, but instead of using a piece of wire as jewelry, a metal plate (usually carved into some sort of design) is embedded into the skin. Popular locations are the same as stapling, but may also be seen covering nipples or navels.
Flesh coils are a blending of traditional piercing and pocketing: instead of having one piece of jewelry per piercing, flesh coiling refers to having one piece of jewelry shaped like a spring coiled through two or more piercings. Think three eyebrow piercings parallel to each other, with one spring-shaped piece of metal connecting them. The ends of the coil are pocketed, instead of going completely through the skin one more time and ending on the exterior of the flesh. As these seem to be the least common of the newest mods, I've only seen a flesh coil through an eyebrow, though it seems possible to do anywhere a surface piercing is possible.
Implants are basically a bit of metal placed completely underneath your skin. Often a parallel row of bars will be inserted under the skin to created a ribbed texture, but there are many variations possible on this one technique. For bar insertion, a deep narrow incision is made in the flesh (with a piercing needle if the implant is small enough, otherwise with a scalpel; the hole may be widened using a taper), and the bar (or what have you) is slid into the incision. Stitches are sometimes needed to hasten the healing of the incision. I have seen these on the forearms, wrists, upper chest, hand, and even upper ear cartilage and forehead. They can be very elaborate and are sometimes called 3D art implants. Surprisingly enough, they are easily removed, though it may require stitches and leave a few scars. The largest risk with implanting is infection due to unsterile materials.
Transdermal implants are similar to the implants described above, except part of the implant passes through the skin and is exposed. A common practice is getting a socket implanted into your scalp so you can screw in a spike (think Darth Maul; yes, people actually have those) or bolt, but weaving (see below) is also an example of a transdermal implant. Transdemal implants are popular on the scalp and all around the back, neck, shoulders, torso, arms, and wrists.
Beading (or pearling) is a form of implanting, except instead of having a bar inserted under your skin, a bead or two is. This procedure differs from other transplant procedures in that a normal wide-gauge piercing needle is used to pierce a long tunnel through the flesh, and the glass, plastic or steel bead is inserted into the tunnel. The entrance and exit points of the tunnel heal up, and the bead ends up under the skin with nowhere to go. Beading is most commonly done on the skin of the penis to increase sexual pleasure of both partners (though much evidence suggests it makes the act more painful), but it's also done on the hands or anywhere else implants are possible. Because of the nature of the skin on the penis, the bead may move around during sexual intercourse. Penile beading has been practiced in Southeast Asian countries for a long time, most commonly in Thailand where it is called fang muk ("inserting pearls"); it was first brought into the eye of the Western public in 1990 during research on risky sexual behaivior and HIV infection. The practice is known as bulletus in the Philippines and chagan balls in Korea and is generally more common among the lower social classes or blue-collar workers.
Surface weaving is the connecting of several surface piercings with one long strand of Teflon or silicone: sort of like a mix of surface piercing and flesh coils. They're said to hurt quite a bit and can leave bad bruises. Weaving is popular on the outer arms and around the neck, wrists and ankles. I have also seen weaving between many people as a part of a religious ritual (five piercings each on five people, all woven together to form a pentagrammaton pretty cool). For a more permanent weaving, a small chain may be used in place of a strand of plastic (see below for more on chain piercing). Somewhat related to surface weaving is the practice of sewing shut one's mouth, as part of BDSM or fetish play or a religious ritual (it's said to be an intense metaphysical experience, and also looks freaky).
Chain piercing is more permanent than any of the above modifications. This form of piercing is identical to traditional piercing except that instead of a solid piece of metal or plastic for jewelry, a small chain is inserted. Over time the flesh will grow around and through the links of the chain, effectively permanently embedding the chain into the skin.
Mods such as these are so involved they usually look more like a surgical procedure than your everyday lip or nipple piercing. I have heard of a few people doing simple procedures (like pocketing or stapling) themselves, but it is not a good idea at all, especially with more complicated procedures like weaving or implants: if you're planning on getting any one of these, go to a piercing studio. You'll be glad you did. A long amount of time for prepping for any of these procedures is normal, including drawing and erasing and redrawing a lot of little lines on the area to be pierced to make sure the jewelry will sit in exactly the right place. A lot of the time they bleed quite a bit, especially the more involved surface-related piercings, and usually aren't that comfortable. All of these aren't technically completely permanent, even chain piercing, but removing them would require a surgeon of some sort, quite a bit of time, would probably cost you a lot of money and pain, and would definitely leave some big weird scars. Don't get any of these if you're not sure about it, or if you'd have to remove it to go back to work on Monday.
For those who enjoyed this node and want more, damnit, here are some ideas to roll around in your head.
Extreme "traditional" piercing: mandible, clavicle
Weird "traditional" piercings: eyelid piercing
Extreme surface piercings: brace piercing, scalpellng, Mad Max 4- or 8-point bar, corset piercings
Body reshaping: ear sculpting, sounding, head splitting, meatotomy, subincision, biurification (all really permanent, if done right)
Pictures of the practices I outlined above are available at the sites below. Be warned, some of the pictures are very graphic and may contain nudity.
Mad Max Tattoo: Unusual Piercing (http://www.madmaxtattoo.com/html_eng/Lavistys_HTML/Unusual.htm)
Mad Max Tatooo: Implants (http://www.madmaxtattoo.com/html_eng/implantit.htm)
BMEzine: Stapling, Pocketing, Plating and Coils Gallery & Experiences (http://www.bmezine.com/pocket/index.html)
BMEzine: Surface & Unusual Piercings Gallery & Experiences (http://www.bmezine.com/pierce/11-surface/bme-pg11.html)
Order of ChAos: Pentagrammaton Chakra Weaving (http://www.crossroads.wild.net.au/pent.htm)
2 July 02: More information about the roots of beading thanks to Roninspoon.