-I started with an appearance in this case. I was watching Hellsing/Hellsing Ultimate at the time and really liked Alucard's design.
-I take an old race idea I had for an RPG, the "Enigma" as I called them way back then. On a whim, I changed their name to Espers. I apply said race to Alucard's design. Hm. I want this character to have blue hair; they tend to have awkward hair colors. One of their predominant features are their catlike red eyes. The story I want this character in (at the time) takes place on a modernish Earth, where aliens and other creatures are unknown by most of the population. I really like Alucard's sunglasses, let's keep those - they'll let him hide his eyes. Heck, let's make him light-sensitive too; another reason for the shades and a legit excuse.
-Tone down the victorian a tad. Remove red longcoat; replace with more modern red longcoat. Oh hey, maybe that was an old science coat from like the 60s or something - the design in my head looks kinda like something Area 51ish. Sure, let's say he found it when he arrived at Earth and took a liking to it. Maybe his race is used to warmer temperatures too. Yeah, that'll do.
-Remove floppy red hat. I love that thing but there are limits.
-Make his hair messier! And shorter. He seems like the kind of character who would have messy hair.
Okay let's leave the visuals there for now. Name? Personality?
-Well in the old RPG I had a Enigma/Esper character named Aris. I like that name, but it's too short. Combine it with random things... Most of these sound terrible. I used to use the name Shade online. Shadearis? Sounds weird. Shaadaris? Ooo, nice. I like it. Let's go with that! Shaadaris Cerq!
-Personality? Well in the story this guy pretty much doomed his race to destruction in order to stop them from invading Earth as a new home for their species. I imagine he'd be pretty broken up over that. Kinda depressed on the inside; but he's polite - why? Very proper upbringing. How about royalty? Sure. As such, he hides his despair behind a friendly and calm exterior. Kind of a cloudcuckoolander - he is from another world after all - doesn't understand human culture, not good with their languages, figures of speech confuse him.
Etc. Etc.
I just keep changing things, removing/adding, making big and little edits until I have a character I'm satisfied with as being different enough from the original idea..
While it may not be in order, this is pretty much how I came up with the original drafts for the character Shaadaris. Starting with something, changing it until it's completely different.