RPG'ers are actually fairly 'common', actually. However, they tend to be in close nit groups who rarely venture out into the wild. Also, because it's still small'ish in numbers, people/groups tend to get a "reputation"; basically, styles of play. Me and my group enjoy generally "unforgiving" campaigns (think Olde Skool), and there aren't many other folks who enjoy it. Those that do...well, they have their own groups. So finding others who are willing to "give old skool a try" tend to be...rare.
I'm not an 'old school' gamer, but I think I would question whether a highly deadly game and allowing player options are mutually exclusive ideals. If you guys need players for your group and you have a small population to draw from, then I would encourage you to boil your game down to its essential component and market that. From what you're saying, I think you run a very lethal game. I would market that.
Past that, I would encourage you to try and reconsider your perspective on player options. When you allow a player to play a certain race or archetype that isn't in the PHB, you are not allowing every other published option to enter your world. You're allowing that one option. Just like you would with a homebrew. Have a conversation with the player and figure out why they want to play a particular option.
Maybe they want to play a goliath because they love the idea of this hulking brute and like that the mechanics help reinforce that concept. They may not be interested in the nomadic giant-kin angle. If your world doesn't have goliaths as a race, then you can offer him the mechanics as an altered human (7th son of a 7th son? Magical tomfoolery?). Make a hook of it.
If it's the flavor of the wandering tribe and the mechanics don't matter to him, then offer a similar option to him within your world. Maybe there's a tribe of nomads who serve some stone giants in the northern mountains of your world.
Or, you can go the easiest route and just say that there are a small minority of goliaths that exist in distant areas. Maybe this guy is the only one that's been seen in these lands. That's a pretty interesting hook.
But, allowing goliaths doesn't mean that you're also introducing Firbolgs, Aaracockra, Duergar, Tabaxi, etc... You're expanding your world to make sure that your player can find his place, his fantasy, in it.
A D&D group is about relationships, right? The best groups like each other and work together to make sure that everyone is having fun. When you're looking for new players, be abundantly clear about your group's identity (highly deadly), but past that, make sure there is room for their fantasy within that identity. Ideally, you're going to be the DM for these players. You want a good relationship with them. Work with them and build that relationship. If they're a good player, they'll be willing to compromise with you too. A good player doesn't want to join a game and upset everything. However, every player wants to express himself through his character and play something that engages his imagination for whatever reason. There's room to meet in the middle.
I recognize that advice is more work than laying out a long list of what you want and that it may involve some compromise on your part. However, if you're in an environment where players are scarce then you may need to be more flexible in some areas to grow your group. I believe you can do that without sacrificing the core identity of your group. If you were in a high population area (or playing online), then you might be able to get that group of ideal players. If you're on the internet advertising, you might be able to find the five other people in the world who always wanted to run an all gnome bard party in the whole world, right? But, if your potential playerbase is much smaller, then you have to cast a wider net to get what you want.