1. Include an extra 32-bits of address information as an IP options header. Call it an IP4.4 packet.
2. (I think?) IP4.4 packets would therefore happily travel over existing IP4 infrastructure.
3. Each existing IP4 address becomes a potential IP4.4 network with 32-bits of address space behind it.
IP4.4 aware routers at the network border could swap inbound IP4 destination with the .4 address before forwarding on to the internal network. Basically like NAT, but you can allow inbound connections without maintaining state.
EDIT: formatting