What methods to determine longitude can be used in a medieval (1400-1500) world? How long would these methods take to learn, and how accurate would they be?
They did calculate longitude in those times. The trick was using celestial objects other than the stars which moved over time. Several methods are mentioned in Wikipedia's History of Longitude. In particular:
The first publication of a method of determining time by observing the position of the Earth's moon was ... published at Nuremberg in 1514. The method was discussed in detail by Petrus Apianus in his Cosmographicus liber (Landshut 1524).
The older methods had limited accuracy. The quality of our longitude measurements increased over time, culminating in the marine chronometer, which decoupled our measurement of time from the skies.
The accuracy of these methods was dependent on the quality of your optics and skill with the tools, but was generally acceptable for navigation purposes. The real limiting factor was the time it took:
The lunar distance method was initially labour-intensive because of the time-consuming complexity of the calculations for the Moon's position. Early trials of the method could involve four hours of effort. However, the publication of the Nautical Almanac starting in 1767 provided tables of pre-calculated distances of the Moon from various celestial objects at three-hour intervals for every day of the year, making the process practical by reducing the time for calculations to less than 30 minutes and as little as ten minutes with some efficient tabular methods. Lunar distances were widely used at sea from 1767 to about 1905. With the new tables with Haversines from Josef de Mendoza y Ríos (1805), computation time was reduced to a few minutes.
The simplest and oldest method of estimating longitude was dead reckoning.
Determine your course from the sun at midday, determine your speed by paying out a log on a string (perhaps a string with 'knots' on it), determine the time by counting the days. Multiply speed by time, then at noon each day, assume you are that distance in your given direction from where you were one day ago. Assuming you start at a known longitude (port), just keep adding your estimates for each day.
To make things simpler, you could always travel on straight lines of latitude. Latitude is easy to calculate from the height of the sun, so if you make sure the sun is at the same height each day at noon, then you are following a latitude line directly East or West. Then you don't have to worry about direction, just speed per day.
It doesn't sound like a great method (and it wasn't) but it was generally good enough to get anywhere around the world. After all, hundreds of European vessels using exactly that dead reckoning method found their way to the Americas or the Indies with a few decades of discovery.