The solution is preprints. Once you publish a preprint (through either arXiv or your own university server, although I recommend arXiv), you have a source to cite in the second paper and you can forget about the need of having it published before the other.