@maunzi I use Brouter [http://brouter.de/] together with OsmAndm with my own biking profile (adapted from the trekking Brouter profile).

When Brouter is installed, you can select it in an Osmand routing profile as routing engine. Not very user-friendly, but with the own profile I get the cycling routes which are absolutely perfect for me, and it's working everywhere :) Can share my Brouter profile if you're interested.