The Long Way to Build New Names
The IPA chart show below describes every sound that the human body is capable of making and uses in the course of verbal communication. Every language uses a subset of these sounds.
There is a newer 2015 revision but I couldn't find a good legible copy.
Of this huge set of possible sounds, each language chooses some to use. Below is the English IPA chart.

As you can see there are a great many sounds that English just simply does not use and, if you are targeting an English audience, you shouldn't expect them to pronounce your new names "properly".
Have a look at the IPA symbols with pronunciations.
Name Generation Process
Here we go:
- Look through the GMU Accent Archive where the IPA charts for many many languages can be found. Familiarize yourself with the languages / dialects / accents you are most familiar with. If you find a particularly interesting IPA sound set, go find examples of it on YouTube (or your favorite video site).
- Take some time to learn what the IPA symbols mean and how they sound. Wikipedia has lots of sound samples for consonants and vowels.
- Pick a collection of random consonants, at least 15, at most 25. (But go nuts if you want to) It doesn't yet matter if your target language uses or can even hear those sounds, we'll get to that later. (For example, a monoglot English speaker most likely won't be able to tell the difference between a plosive glottal and a fricative glottal. Right now, we don't care.)
- Choose some vowels, probably no more than 12 but no fewer than 5.
- Decide on a few rules about which sounds can or can't follow other sounds. For example, maybe you want a really fast sounding language, so have a rule that says consonants must come in threes with no intervening vowels. Or, each consonant must be followed by a vowel and vowels are never allowed to start a word. Go as crazy as you want but remember that you will need to rein in any craziness here when you get to the transliteration step. Don't make yourself work any harder than you have to....unless you really want to.
- Create some candidate names using the symbols you've come up with. If the randomness is weak with you, assign each symbol a number then choose a random integer from Random.org. Sometimes the resulting words won't make sense, such as if you get 5 consonants next to each other (unless you're Czech, in which case, go for it!). Use your good judgement here.
- Evaluate the emotional feel of your names. Note that every culture places an emotional value on a particular kind of sound. I'm sure you can think of a language that always sounds angry (to you) for no other reason than the sounds of that language, even if the speaker isn't angry. This step is highly dependent on your needs and the needs of your audience.
- If you're happy with your sound set, go ahead to the transliteration stage. If not, go back to step 3 then refine your sound set or choose new random names.
So we have the sounds and names, but they are in a language that are probably only pronounceable by you. Let's fix that with a little transliteration:
- Map each of your chosen symbols to the sounds that closely match your target language. There may not be any close relationship, so you'll need to approximate and get close. You may lose some vocal nuance such as if, for example, you have to collapse a voiced and unvoiced dental fricative down to just a voiced dental fricative. If this is a problem, go back to step 3 and refine your sound set.
- Now, take the sounds in your set and assign them to the letters and letter combos of your target language.
- Translate from your IPA symbol set to your target language for each name you need to generate.
- By this point, you should have some very unusual sounding names that aren't based on any single Earth culture but have the emotional feel you want.
Maintaining Pronunciation
As you can see, it's incredibly easy to choose a selection of sounds that are completely unpronounceable by your target audience. Don't make that mistake. If your audience can't even say your character's names, they are less likely to talk about them.
Extended Language Exercises
This same process can be used to generate a new language too though that will require generating an entire new set of words. Just start with translating the ten hundred most common words of Up-Goer Five.