How can I set up a 6to4 tunnel (NAT traversal)? I'd like to get IPv6 including NAT traversal on my Android phone. Root is available.

It is so easy to get a 6to4 tunnel on Linux.. Just install aiccu and then aiccu start. On Windows there is gogoClient which is also quite easy.

I tested IPv6config but my phone does not work out of the box and the author seems more interested in a proof of concept rather than supporting all phones. He does not reply to my e-mails, and after Googling this app it seems that I am the only one using it.

Are there any working ways to setup a 6to4 IPv6 tunnel on Android?
The title of this post says "6to4 (NAT traversal)". This is fundamentally impossible. It does not work on your standard Linux, let alone Android. The 6to4 protocol relies on having a public IPv4 address on the same machine you terminate the tunnel on.

Leaving that aside, it may be that you are simply using the word "6to4" when in fact you mean "IPv6 tunnelling". Other tools, such as AICCU or gogoc, utilise different protocols that encapsulate IPv6 within UDP within IPv4 to allow the NAT traversal to work. These do not use 6to4.

Your Android distribution must support the necessary kernel modules for tunnelling to work. You must have the sit module available for 6to4 (or the tun module for many VPN products, and so on and so forth) as well as the ability to add tunnels such as via ip tunnel add mode sit. It may be that you do not have that available.

I have a device (Motorola Milestone running CM7) that is supported by the IPv6Config app you mentioned above. The app does not appear to do anything phone-specific. I suspect that the fundamental problem is that simply having "root" on your phone is not enough — your Android must ship with the appropriate kernel modules.

You may need to run another distro (e.g. CyanogenMod instead of a rooted stock Android) that includes the proper support to allow such tunnelling to work.