About 10 years ago I cycled from Amsterdam, up the Rhine valley, and eventually to Munich. I started it in late April, and the weather was reasonable - not many rainy days and reasonable temperatures, but I can't remember any detailed stats. A good place for those is the BBC's weather site which gives historic average temperatures and rainfall for each month in many international cities. Alternatively, why not give the southern half of Europe a try?

The one thing that I did find bike-touring at that time of year was that many campgrounds had only just opened for the season, so beware if you are planning to use those.