Hi Oliver,
I am not a lawyer, and this is not legal advice. If you want to be absolutely certain, get some professional advice from an attorney experienced with game development.
That being said, you do need permission to use characters from an existing game, and unfortunately for you it's pretty rare for that permission to be given unless you are an experienced developer with a proven track record. In the case that they are willing to grant permission, there may also be a monetary cost involved. This applies regardless of whether or not your game is free or for profit. Nintendo are pretty well known for being quite strict with enforcing their intellectual property rights.
If you use a character without permission and it comes to the company's attention, they will usually send you a cease and desist notice telling you to stop using their intellectual property in your project. If you ignore or choose to fight this -- or at their discretion, without even sending a notice first at all -- they can take you to court, where losing the case could potentially cost you quite a bit of money. Even if you were in the right, the cost of defending yourself may be more than you would be willing to pay.
Now, with that (probably depressing) news out of the way, if you really want to try there's no harm in asking in a business-like manner. They receive these sort of requests all the time, and there's no need to be embarrassed -- the worst that will happen is that they will politely decline, but who knows -- you just might get lucky.
I also have a couple of links for you!
Sorry if that's not the answer you really wanted, but I hope that's helpful!