I've always quite liked http://cycle.travel - UK oriented but the map interface is OpenStreetMap based so can handle overseas as well. Website not an app, but may still be useful.

It defaults to off-main-road and includes a very useful height mapper display, so you can tweak a proposed route to avoid steep hills.