While pixel perfick's response is commonly accepted practice amongst many hobbyists and would probably be good enough to keep you out of trouble, it's not strictly correct.
If your work is based on an existing piece -- even if you create the new piece completely from scratch; drawing your own version of Mario for example -- it is considered to be a derivative work, and you risk running afoul of copyright infringement. This covers your numbers 2, 3 and 4 situations, and technically there is no amount of changes you can make to the work that makes it legally ok -- the only way you can safely use someone else's copyrighted work is to get permission*. In practice of course, if you make enough changes the work won't be recognisable as something based on the original and you wouldn't be taken to court.
Your current situation (listed as #1 in your post) however is not a derivative work; you created your character completely independently and without intention of copying existing work, and only later realised it is similar to the existing character. Technically you're in the right and aren't violating copyright. Unfortunately however this still doesn't guarantee you're safe from legal action...
You can be sued for any (vaguely rational) reason at all, and even if you're 100% in the right you could still be taken to court. If you're really in the right hopefully the judge would decide in your favour, but the process of going through the court case may still be quite expensive, especially if you're fighting a large company.
If a company thinks you're using their work, or a derivative there-of they will usually send you a cease & desist letter asking you to stop; they can however simply choose to skip this step and go straight to legal action, in which case they would file a case against you. It's then up to the judge who hears the case to decide whether or not you are actually infringing and if you are to award damages you would have to pay. If you're just a fan with good intentions and you haven't made much (or any) money from your game, you would be forced to cease your project, but probably wouldn't have to pay a lot in damages. However, if you've done as Pixel perfick suggests above and given credit to the original creator it may be decided that your infringement was "willful infringement", which can potentially result in much higher damages being awarded.
It's up to you to decide what's an acceptable level of risk to take, and if you'd like to be more certain you should speak to a lawyer experienced in video games and entertainment -- you can find a list HERE. Is your character similar enough that an employee of the company is question is likely to genuinely think you've ripped off their work, and are you using it in a way that they would be likely to object to? You could spend forever trying to play it completely safe, but there will always be some minimal level of risk -- it sounds like you genuinely didn't copy anything in this particular case, so unless your character is bears a striking resemblance it's probably a pretty low risk to take.
Hope that's helpful! <img src="smileys/smiley1.gif" border="0" align="middle">
* Technically there is another way you can safely copy a copyrighted work without permission; Fair Use. Unfortunately however this is not a protection you can reliably depend on without legal advice, as only a judge is able to rule whether or not your particular usage qualifies, so you would have to be taken to court before finding out if Fair Use applies.