1. User negotiates with n number of nlocktime-relay nodes and receives their fee address
2. User creates n number of tx's, each with a standard fee and an output to the nlocktime-relay's address
Yes that would work however it would be rather inefficient. User would need to locate a number of relay providers, create multiple modified copies of the same base tx and send a copy to each relay provider.