Usually that kind of work is done by a marketing team, and indeed it's a very big challenge to do all this by yourself. And a huge responsibility.
In general, the whole process is an information gathering one, and then an elimination phase. And you do this for each aspect of the brand (eg. color, sounds, names, logo style, etc.)
Look at what the competitors do
What the marketing team would do is to look at the other companies offering similar products or services as the company asking you for this task. Note down your observations, see what was already done and what direction the competitors took. with this it will also give you clues on what to not do.
You should put on paper some keywords as well.
To get you started, you should explore what keywords will fit the service or product your client is offering. It can be things like "fresh", "young", "powerful", etc. These will help you to find icons, fonts, concepts that could inspire your for the name of the brand and the logo. The keywords are going to be your starting point for the brainstorm and the next steps.
Have fun exploring the words, looking online for what comes up when you search them and save these urls, images or take screenshots; you'll probably need to look at them a few times. Usually choosing keywords has a domino effect; you'll think of a keyword and then from looking at all your keywords, you will see a pattern emerge or think or new keywords.
By searching online for these keywords, you'll also see what kind of concept, images or ideas are associated with them. You might end up seeing some keywords are not acceptable because they're associated to religious ideology or unconventional activities or groups you don't want the brand to be associated to.
Explore the target market
Find who this product is targeting, and note down the things you think they will associate with a positive feelings and the ones with negative feelings.
Look at what that market is interested in, what are the strategies others targeting them use, how they reach them, what music they like, what do they watch, etc. Some things here I'm mentioning might seem totally useless but the point is simply to immerse your brain into their world and try to discover what will reach that market.
For the colors, you can have a look at "Kuler" online for interesting choice of palettes, and think of the keywords you previously found to match a set of colors that can fit them. For example, if the company is selling cleaning products, you might want to stick to cold tones or blue, anything that will instantly give that image in the mind of the person looking at it.
You will avoid colors that give a contradictory feeling to the main mission of the company; using red for a spa salon might not be a good idea because of how red is associated with energy and danger, using beige or yellow for teeth cleaning products isn't a good idea either for obvious reasons! Already this should give you some idea of the way to go with the colors. And these colors might also bring you extra ideas about new keywords or concept.
In general, you should try to find colors that will be easy to print, have a good contrast, not too trendy, etc. But at this point, it's not that important to select the color for the logo; the colors now are only there to help you get more ideas about your brand and inspire you.
This is probably the hardest part. Usually designers already have a name for the brand and this is their starting point. But you already collected some ideas about the colors, some keywords and concepts, you know how the competitors are named, you know a bit more about the target market, etc.
The client wants a name for the brand that is international english. That already gives you some clues on what NOT to do, since you don't know yet what to do! Again, you can start by eliminating options if you're starting with a blank sheet for this. You know for example words like "color" or "colours", words with "z" or other uk/usa words will automatically stick a label on your brand if you use them. You can make a little search to see what are those words and eliminate them from the list OR totaly modify them in order to remove that label (eg. UK english or US english.) Maybe you could also search on linguistic forums for this.
Even if you're targeting an english speaking market, there's still sounds that some languages cannot pronounce easily. On the european market, a lot of people use english as a second language, that's why it's good to try to also think about this if you can.
And for the general idea of the name, you will use the ideas you got from your keywords search, images and avoid the words I mentioned above that could be confusing. I think for this part, you should take your time and let your ideas float in your mind a bit, and take notes when you have a new idea that comes up. You'll probably end up with a few potentially good names and ultimately, it's the client who will probably select the winner; maybe even come up with a "better" name. So don't try yet to find the perfect name unless the client really let you choose this without any restrictions. I would definitely have the name approved before starting the logo and I'm guessing the client wants you to do the research part and come back to him with some options that you will adjust according to his feedback.
If the name you're looking for could be used as a verb (eg. Google, googling) or a totally new product that could become the main way to name such a product (eg. Kleenex for tissues), you can explore this to find something original, and think of the many ways the name could be used.
If you're alone, it's harder but you can still gather some useful info to show to the client who hired your for this project, and then see his feedback on this. And then do another search.
Before you meet your client, you should gather all your elements, and prepare a presentation to explain the concept. Bring you color swatches, tell the idea behind your selection and mention what direction you want to go with this and how you came up to this conclusion. what you want is to make your client visualize what his brand is going to be, and he will definitely pitch in what this inspires him. He also knows his business. A few brainstorms are usually necessary and ideal, but if you cannot have this opportunity to get some feedback, then you might need to do this process a few time yourself and go by elimination.
There's way more to creating a good brand but this should already get your started. And if you can do it with a team or have some friends to give you some feedback, ask them. Sometimes only simple questions such as "what do you think of when I tell you the word XXXXXX?" is already a good way to collect other ideas you might not have think of.
Note on domain name
It should be easy but still try to find something short, and avoid weird extensions that are not .com if possible.
Think of how easy it will be to say that domain name on the phone without having to always spell it out, how it will be short enough to be easy to put on a business card and to remember.
If you're worried about finding a good domain name available, sometimes some domain search offer suggestions when searching for terms and this can help a lot. You can also combine a small verb with the domain name (eg. the verb "go" or "get" or need", etc.)
Copyright/Trademark (Intellectual property)
There's online database for this, you can have a look at. That's a big task to search for this... that's why you should maybe create a brand name that uses new words instead of matching 2 known words. Otherwise you might spend a lot of time simply searching for names.
It's not the perfect solution, but if you already create logos, it's basically the same principle as you can see and most of the work has to do with researching elements to make the ideas come to you instead of trying to force them out of you!
I hope this helps, good luck with that huge challenge!