The requirement for no middle man can be interpreted in different ways. And which exact interpretation is being used does make a difference, because certain interpretations will in combination with the other requirements result in an impossible set of requirements.
Considering the ISP providing internet connectivity to each endpoint to be a third party that cannot be relied upon is obviously too strict to allow for communication. But even if we include the routers on the IPv4 path between the endpoints in the infrastructure we can rely upon, it remains impossible due to the other requirements:
- Bob wants to initiate the connection.
- Bob can only send IPv4 packets.
- Bob does not know any IPv4 address to send the packets to.
If we interpret the no middle man requirement to simply say that the bulk of the traffic must not be routed through a third party, but it is acceptable to involve a third party in connection setup, then it is possible.
Bob can send a packet to a third party on a public IPv4 address asking for a message to be send to Alice' IPv6 address asking Alice to connect back to Bob over IPv4. In any new protocol design intended to be future proof, I would only use the IPv4 connection between the endpoints as a means of tunneling IPv6 packets and then let all the higher layers deal only with IPv6.
Which IPv6 tunnel protocols might be suitable
Let's consider the following options for Bob getting an IPv6 address that can be used for the bulk transport: 6to4, 6rd, 6in4, native, Teredo, home grown.
Lack of support from Bob's ISP immediately rules out 6rd and native.
The requirement for no third party rules out 6in4 unless one of the ISPs on the direct path between Alice and Bob offers 6in4 which Bob can use. Such service is unlikely to exist on the direct path, and if it did would require more configuration on Bob's part, then I think you'd be willing to.
The requirement for no third party also means that 6to4 and Teredo are potentially problematic.
Anything using protocol 41 is difficult to get through a NAT. And even if you can get it to work through a NAT, it can in most cases only support a single user behind the NAT. Given that Alice can't even get a port forwarding, we can pretty much rule out using protocol 41 end-to-end. Thus goes 6in4 and 6to4 as possible end-to-end communication.
Setting up anything based on protocol 41 requires administrator privileges on the endpoint where you are configuring it. This is another argument against 6in4, 6rd, and 6to4. A tunnel based on UDP can be built directly into the application because UDP ports can be opened by an unprivileged application.
Using 6to4 on Bob's side with native IPv6 on Alice' side means relays must be used. Since I argued that Alice can't send protocol 41 packets, Alice would have to rely on a relay operated by somebody else. With a bit of luck Alice' ISP has a relay, but you can't rely on that. It is not much better in the other direction since Bob's ISP doesn't support IPv6 at all, they are unlikely to have any relay either. So 6to4 in this scenario is likely to have problems in both directions. That rules out 6to4.
What we are left with from the starting list is Teredo or homegrown. If Bob uses Teredo, his first packet will be sent to a Teredo server chosen by Bob. Since Bob can choose which Teredo server to use, the use of a third party would be less of a problem. If a third party turns out to be unreliable, Bob can simply switch to another.
But that only covers the first packet from Bob to Alice. The return path is a bit problematic. If you simply rely on the default routing, then the return traffic from Alice will go to a Teredo relay operated by Alice' ISP or much more likely a third party relay. If Alice' ISP has deployed enough Teredo relays to handle their customers' traffic and they are paying attention to the stability of the relays, then Teredo would reliable in this scenario. However such ISPs are rare.
Alice could decide to run her own relay. But connectivity between Teredo client (running on Bob's computer) and Teredo relay (running on Alice' computer) is usually opened from client to relay. That is the direction, which did not work for you.
There is a deprecated mode of operation in Teredo in which connections can be opened in the other direction from relay to client.
This means you could build a Teredo client directly into your software and in the specific setup you describe have it use this deprecated mode on Bob's computer. On Alice' end your software runs on a native IPv6 address, but at the same time your software must detect peers using this deprecated mode of Teredo and when detected attempt to send packets directly to the peer using a Teredo relay build directly into your software.
One caveat you have to pay attention to is that when the first echo request from Bob is sent through a Teredo server to Alice, it will be processed by the IPv6 stack in the OS on Alice computer rather than by your application. That means it will be tricky to get the reply routed through a Teredo relay build into your software.
If you take this approach I strongly recommend that you write your software to support sending packets either through your build in Teredo code or through the ordinary route. And periodically probe both ways to send packets such that you will always be using the most reliable of the two.
It's a bit ironic, that of all the standard protocols I can think of, the one which fits your requirements the best happens to be a deprecated variant of Teredo. Even more so considering that Teredo is usually considered to be unreliable. That said, I truly believe that under the exact circumstances you describe, it could be made to work reliably.
A possible homegrown solution
You could pick a /80 prefix of RFC 4193 address space to use in your application, and use the last 16 bits of the IPv6 address to embed IPv4 address and port number of a tunnel endpoint.
With that approach, Bob would have an IPv6 address which Alice could send packets to. The problem with this approach is, that Bob would not have any way to send IPv6 packets to Alice before having reached the first IPv6 packet from Alice.
Also being homegrown, there are no public servers which can relay those packets from Bob to Alice. So this particular homegrown approach would be like Teredo except that the problem about insufficient infrastructure would be amplified.
Based on that, I am thinking that if you want to go with a homegrown solution, you are more likely to get a good result by taking Teredo as a starting point and try to improve it rather than building a homegrown solution from scratch.