How could one insulate sill plate from the outside?
Since all you need to do is keep out air here (not actually insulate it), and you need it to be durable to the elements and fauna, I'd suggest filling that gap with mortar or quick-setting concrete. Once it's fully sealed up on the exterior, you can go inside and seal up any remaining gap with Great Stuff or another kind of expanding spray foam, or even caulk if the gap is small enough.

If you want to go even farther and actually insulate the sill plate and band joists from the inside (a good idea), you can do as your first picture suggests and encapsulate them with even more spray foam, or you can cut pieces of rigid foam to the right size and caulk them into place so they're airtight. The point is that if you insulate the sill plate and rim joists, you need to make them completely airtight from interior air, which is moisture-bearing and can condense on them if you insulate them without cutting them off from interior air. Once you've 100% sealed them from interior air with spray foam or caulked rigid foam, you can fill the remainder of the space with cheaper mineral wool or fiberglass batt insulation. Use only unfaced batts.

Another thing to keep in mind. You mentioned that you feel a draft when the gas fireplace is on. Gas combustion consumes air, and that air has to come from somewhere. I'm guessing that your gas fireplace doesn't have its own ducted supply of combustion air, so the air is coming from inside the house, from the biggest nearby air leak--the one you're asking about. If you seal off that air leak (a good idea), the air will be pulled from somewhere else. If you seal off enough of these air leaks (a good idea), your gas fireplace may be starved of air and cause backdrafting of any other gas combustion appliances inside the house. This is very dangerous, but probably not something to worry about right now. However, keep in mind that the tighter you make your house, the more you will need to confront this challenge/danger. The fact of the matter is that gas appliances without ducted outside combustion air supply are not a very good match for being located inside tightly sealed houses.