Yeh. Basically you need some way that can do a IPv6 tunnel that's NAT traversal capable. 6in4 really isn't. To have a many-to-one NAT work, a firewall needs something to identify internal hosts' connections for return traffic, since all the return traffic comes back to the same public IP.
With TCP and UDP that's possible, since it simply uses the source port of the traffic and
in effect extends the IPv4 address by two bytes. The NAT box will note the source port traffic went out on to say, a web server, and when that traffic returns, it will have a source port of 80, and the destination port will use the source port that the traffic went out on. So then it just looks up who used that source port in a connection table, and thus figures out who sent that traffic out, and routes it back to that internal IP. 6in4 doesn't have ports, so there's nothing for a NAT box to use to uniquely identify the return traffic. Therefore, there can only be one session through one public IPv4. That old post I made suggested that FW NAT implementations could use the IPv6 address in the 6in4 packets to identify the inside hosts, and be able to handle multiple 6in4 connections in cases like yours. But a lot of people seemed to resist the idea for some reason.

Teredo should work for you as long as your firewall doesn't have a symmetric NAT setup, and it's not being blocked. Teredo tunnels IPv6 through UDP which is NAT traversal friendly. But Teredo would be even slower. And also, under windows, most apps won't use a Teredo IPv6 connection when there's an IPv4 address available because windows is set up so that each application must say "it's OK to use Teredo". Not sure if there's a way to globally change that, but you wouldn't want to anyway, since Teredo is usually pretty darn slow.
PPTP might have worked for you, since although PPTP uses GRE which isn't exactly NAT friendly, most firewall devices have a PPTP specific "fixup" for it that uses fields inside the PPTP/GRE packet to associate with and identify each session/internal host to allow NAT traversal. But unfortunately HE has suspended PPTP.
I really think HE should put out something that uses UDP or TCP for tunneling. Maybe AYIYA or something like that.