You can easily do this with ortho litho film if you need to go the contact print method. In my class I taught today we contacted printed cyanotypes with images created on ortholitho film in the darkroom. It was the end of the box of Arista branded litho film, and I have just ordered a box of 100 8x10 sheets from photo warehouse (ultrafine film brand) for about $85 plus shipping (ps its cheaper to order off their amazon store as shipping is only $5 instead of the $8 they are charging on their own site, plus you can use your amazon account).

If you dont need to contact print it just take a picture (copy) of your negative on negative film so you get a positive, and print with that.

Your paper to paper method also works well, but its not always the sharpest way. Always emulsion to emulsion, and use a good large piece of glass/plexi glass