How do I submit interdependent papers?
This is one of the things pre-print services can address quite readily, even for fields that don't normally use preprints. Putting both papers on arXiv (or another field-equivelent) allows them to exist in a citable form, and as one or both of them make it through the publication cycle, the linking citation can be updated to reflect this. FigShare will also let you upload documents and provide you with a DOI, though I've never actually seen this done in practice, and it's likely arXiv or an equivalent is more appropriate for a full-sized manuscript.

If you're in a field that has conference presentations and the like that aren't equivalent to publication (for example, much of biomedicine) you may also be able to cite a poster or presentation given at a conference.