The problem was solved by just adding a A-record at 1and1 pointing at Heroku. No nameservers or any extra service needed.
Here is a more detailed update: First you have to go to the Heroku app settings. There you can add domains for your app, like www.mydomain.com.
Then you use a service to get the IP address of the server where your Heroku app instance is running. (Just get the IP address of your instance of yourapp@herokuapp.com.) Then you add this IP address as a A-record to the 1and1 app settings. Now you have to wait for the settings to propagate over the DNS servers.
Basically you point your 1and1 app to the server on which your Heroku app runs and inform your Heroku app that there probably is some app trying to reach through to it, which has a specific address, like www.mydomain.com. That's how they find each other.