I saved these old, stretched out shoes in my closet in the hope they would heal themselves. After giving it a good ten years, they still hadn't spontaneously regenerated and so I was forced to exert some effort.

These shoes were unwearable because they bowed out on the sides and my heels slipped out when I walked. This project solved both problems. It was a lot of fun and very satisfying. I have given myself an official pat on the back for hoarding the shoes and not bowing to my husband's relentless need to throw things out.

The starting point was this blog post on Creative Fashion Blog. I've changed and expanded that project in several important ways to make the shoes sturdier and stylistically different.

Supplies

Pair of old shoes.
Coordinating or contrasting eyelets. I used 3mm black ones. Determine the size you need for your choice of laces by setting them in a sheet of paper and then pulling the cord through. I chose eyelets over grommets because I only needed to fuss with one piece instead of grommets, which have an upper and lower piece. I chose to use coordinating eyelets and cord because 1) I have big feet, 2) I didn't want to make statement shoes, and 3) I know that looking good on the table doesn't necessarily translate to me actually wearing them. Here are the ones I used.
3mm satin cord to coordinate or contrast with your shoes and eyelets. You can use twine (maybe with espadrilles) or ribbon if you want a big bow - just don't over complicate it and make the project harder than it needs to be. If you decide on ribbon, I recommend grosgrain ribbon. It doesn't stretch, is strong, and will last much longer than decorative ribbon. I wouldn't use anything that is very thin because it could dig into your skin or real leather because the dye on the leather could mark you and look ugly. You could use flat laces for a more sporty look. I bought my cord here.
Marking tool - what you use will depend on what material your shoes are made from. Two of mine were patent leather (I used a gold Sharpie) and one was cowhide with fur (I used a chalk marking tool). Marking was by far the most difficult part of the process. You could also use a ballpoint pen or a pencil. The best option is something you can see and will wipe off if you need to adjust the hole placement. I ending up having to cover the gold from the Sharpie with black Sharpie. There are air soluble pens as well, but my shoes were dark so I couldn't use them. In the end, chalk was the best choice. This is the one I used.
Leather punch - Mine has several sizes of punches. I experimented on paper first to determine which size I needed. An awl is not a good choice because you need a hole with space in it for the eyelet to set properly.
Pins to poke the leather centers out of the punching tool.
Eyelet setting tool. There are punch tools that look like a nail and are very cheap, but since you have to use a hammer or mallet, it would be incredibly hard to use those for shoes. Mine is old, but here is a newer model.
Small scissors - you won't be able to get everything out the holes with just the punch. These are for clearing the rest out.
Needlenose pliers - also to help get all the fibers and lining out of the holes.
Ruler or other straight edge.
Super glue - to glue the cord ends to something like my decorative cord covers, to stiffen the ends so they're easier to pull through the eyelets, and so the ends don't unravel.
Metal cord caps - optional. I like the look and I had some on hand. Here are similar ones. You could knot the ends, put beads on the ends, or even tassels. Just know that if you put something with weight on the ends of the cords, the cords may bang on your shoes or feet as you walk. That would drive me nuts.

Step 1: Decide How You Want to Lace Your Shoes

There are many ways to lace a shoe. Things to consider:

Are there any problems in the shoe you want to correct? I needed to pull the shoes in on the sides and to hold my heels in the shoes.
Your personal style and what you plan to wear with the shoes. For example, I am not a bow person so the focus of the lacing was the pattern created by the lacing itself. If I wanted a bow, I would probably have one horizontal band across the top and a second set of eyelets to lace the ribbon/cord through for the bow. I wear these shoes with skinny jeans or shorter skirts and a bow is more feminine than I would wear with those.
Shoe shape. I wanted to lace through the back of my shoes because I like that look, but only the silver patent leather shoes had a high enough back. If you're using shoes with high heals, that may affect design you want to create with the laces.
How much time you have and, be honest, what your attention span is. The more holes, the more difficult the project is and the longer it will take. Although it only took a little more than an hour per pair and I only did one pair a day, I was pretty much over it after the second pair of shoes. Unfortunately, I left the horizontally laced pair for last and it was the most difficult. It's very obvious when the lines aren't straight so marking took a lot of time.
How far apart do you want the laces to be? Do you want them equidistant, paired or another pattern?
Are you making a costume?
Do you want both shoes to match? You might not, particularly if you're making them for a costume.

I tried a crisscross pattern, a simple pattern to hold the heels on, and a horizontal pattern. I made the bows as small as I could get away with and tied them horizontally so they didn't visually stand out from the laces.

Step 2: Mark Your First Eyelet Placement Point

The placement is totally up to you. The two patent leather shoes started with a center hole. That took some considering. The center of the shoe opening isn't the same as the center of the shoe. In addition, the shoe may have stretched out of its original shape. I finally gave up fancy measuring and just used my toes as a guide and eyeballed it. The visual center point came out to close to the space between my second and middle toes.

Step 3: Punch Hole and Set Eyelet

There is no going back after you punch a hole, so make sure you like where you marked. Make sure you have good light so you can see what you're doing. I mean it, check again and again. If you accidentally rub the mark off, check again and remark.

Center the punch (the tool with red handles) over your mark, hold the handles, and lean down hard on a mat covered table. Do not lean down directly on a surface that you care about. I have a self-sealing mat over a work table that can take a beating.

You'll probably hear a snap when you punch through the leather. Take a look at the punch and if there is material plugging the hole, poke it out with the pins. There may be threads and lining that need to be removed from the hole. I pulled them off with the pliers and trimmed them with the scissors. You need to clear every thread and piece of lining out of the hole or the eyelets won't set properly. If they don't, the eyelets could be uncomfortable or simply fall out.

Place the eyelet in the hole, color side out. The eyelet needs to go all the way through to the inside of the shoe. Trim the edges of the shoe lining around the hole if you need to.

To repeat - clean all the bits of lining and thread from the hole before you set the eyelet! This will probably take a few minutes. If the eyelet doesn't set properly with the inner edges rolled outward, as far as I know there is no way to get the eyelet out without wrecking your shoe. No pressure, but you have one chance to get this right. Use good lighting and take your time.

The prong on the setting tool (pink handles) goes through the colored side of the eyelet. Once again, squeeze the handles and put your weight on them down on your surface.

Thread your cord through the hole. I cut the cord on a long, shallow diagonal with just a few threads at the end. I pushed the lace through the eyelet until I got those threads through and pulled on them to get the whole lace through the eyelet. You may need to spit on the cord and roll it between your fingers a bit to get the threads through the eyelet. Once you get those threads through, you're home free. Alternatively, you could stiffen the end of the cord or ribbon with the glue to make it easier to push through the holes.

If you use another material for lacing, you will still need to cut it on a long, shallow diagonal.

Step 4: Determine Placement of the Following Holes

Hold the other end of the cord and figure out where you want it to go into the shoe. Move it around a bit. See what you like. Mark the spot. If I had a chance to do it again, I would probably make the first pair of holes on the patent leather shoes lower down. The cords don't show as much as I would have liked.

Measure, punch, set eyelet, and lace as you go. Don't try to do all the measuring then all the punching, etc. You can do that with the second shoe, but you need to finish each hole separately on the first one so you can get the placement right.

Due to the curvature of the foot and because I wanted my shoes to fit tightly against my feet, the inner holes are closer together than the outer ones. This was necessary to keep the laces straight even though feet are curved.

Step 5: Complete the Second Shoe

Ensure the shoes are lined up by setting the heels against a ruler or other flat edge and perpendicular to it. You can see my ruler at the very bottom of the first photo. This should be done before marking the outer edge and then again before marking the inner edge.
Put shoes outer edge to outer edge and mark the eyelet locations on the second shoe. I've used chalk.
Hold the inner edges together and mark them.
Verify that the markings are in the right places.
Verify at least one more time. Don't rush.
Punch holes.
Set eyelets.
Insert laces.

Step 6: Finish Laces

To determine cord length, put one shoe on and tie it so you get the look you're aiming for. Cut the ends leaving enough length so you can tie them easily. If you're going to finish the lacing with a knot, make sure you include length for that. Cut the cord ends. Cut your second cord using the first one as a guide.

Unless you use pre-made laces, the cord or ribbon will unravel. If you've used ribbon, cut the ends on a diagonal. If you've used cord, seal the ends with glue. If you try to seal the cut ribbon with glue it may darken and show and you may need to cut new laces in the future. You can leave the ends of the cording plain (but sealed), glue cord caps onto them (as I have done), knot them, or add beads then knot.