To answer my own question (somewhat), it is possible to do this with RSA, but most APIs (including the one of OpenSSL's crypto library) need to be "tricked" into doing it. The reason you can generate the public key, given the private key, is that
It is common practive for implementations of RSA to save p and q (those big prime numbers) in the private key data structure.
Since the public key (which consists of the modulus N and some exponent e) is public anyway, there's (usually) no point in choosing an obscure e. Thus, there are a handful of standard values that are used commonly, like 3 or 65537. So even if p and q are unknown, you might be able to "guess" the public exponent.
However, RSA is symmetrical in the sense that anything you encrypt with the public key can be decrypted with the private key and vice versa. So what I've done (I'm a monster) is to let the crypto library generate an RSA key. You can choose your own public exponent there, which will later be used to decrypt (contrary to the normal way). Then, I switch around the public and private exponent in the key data structure.
Some tips for anyone trying to do something similar with the crypto library:
In the RSA data structure, clear out everything but n and e / d, depending on whether you want to encrypt or decrypt with that particular key.
Turn off blinding with RSA_blind_off. It requires the encryption exponent even when decrypting, which is not what we want. Note that this might open you up to some attacks.
If someone needs more help, leave a comment and I'll edit this post with more information.