I think the fantasy game which meets your complete list of requirements is Desolation by Greymalkin Design Studios. Detailed Product Description and Samples
Desolation runs using the Ubiquity Roleplaying System (from Exile Games, makers of Hollow Earth Expedition) which is an incredibly fast and stable system which is easy to learn, but very flexible.
•Supports fantasy settings
Desolation is a fantasy game with two built-in settings to choose from that you can easily ignore if you prefer your own. I will include some details in the rest of this answer, but generally avoid talking about the setting. The default setting is a post-apocalyptic one, mere months after the end of the world. As a result, it has a very sword and sorcery feel in which Conan would feel right at home. The other setting is a very high fantasy world. The game can be easily run from the core book and you need never worry about or bother with the Before, even if you opt to use the world presented for the game.
There are different races of humans, fantasy races, and a solid bestiary of classic and new creatures. Many of these are presented as very new takes on classic types, but the stats of course can be used for whatever you might choose to run them as.
•Little randomization in rolls, anything bell curved is fine (classic
d20, d100 are out). I want dice though, so please save the diceless
systems for another question of mine in near or far future!
Ubiquity is a dice pool system where even numbers are successes. Part of the system's speed is the freedom to 'Take the Average' on non-combat rolls. Difficulty in the system is represented by the numbers of successes needed. I have never played a faster system with less frustration over results for players and GMs. As a perk, it is a clean system that produces easily adjudicated results without layers of math or memory intensive rules, exceptions, explosions or implosions.
Two questions regarding the system's dice mechanic on rpg.stackexchange are listed here and offer further details:
Link One
Link Two
• Generally non-heroic, but supporting such characters.
This one is a little harder, but if Iunderstand your requirement the system still meets your needs. In Ubiquity, characters tend to be specialists. This can be mitigated by setting a lower starting cap on skills, or having them spread their build points out over a wide range of skills. I suspect that you would not need to make any modifications, based on your second point about heroic levels of attributes.
The game also uses a trait called Style Points which are earned in play in a variety of ways with rewards determined by the GM. This lets players invest themselves in actions which are important to them in a way that most systems ignore or handle with less finesse, and it lets the GM adjust the level of lethality if necessary.
•Skill/stat based character development, no classes.
Absolutely
•There should either be no hitpoints, or losing part of the
character's hitpoints should have a negative effect on said
character's performance.
Hit and damage are a single opposed roll, and loss of health levels leads to penalties and unconsciousness before death.
•Fast (or at least not ridiculously slow) combat without gazillion of
statistics, tables and number crunching techniques.
Ubiquity will blow your hair back. It is so fast that I am still surprised at it even though it has been my go-to game now for two years. Combat involves one initiative roll at the start, then declaration, opposed rolls to resolve hit and damage, then repeat as necessary.
•It would be a nice addition if a system does not use too many rolls
to resolve conflicts - again, in DnD you roll twice for an attack:
first is to hit, the other roll is damage. Ideally the success of the
attack roll would also determine the damage.
See above for an emphatic yes.
•A magic system supporting generating spells on the fly would also be
a nice touch but it is not required.
Magic in Ubiquity in general, and Desolation in particular is free-form and easy to manage. There are clear examples of spells, a clear system of assigning the difficulty for casting, and the added touch of making magic dangerous and difficult by having it cause a form of energy backlash which can exhaust incautious casters. This definitely restricts mage characters from running wild, but leaves them with enough kick to be an enjoyable challenge.
NOTES
Availability: The game is available in PDF or hardcover from the usual sources. The Amazon and Publisher links are given above.
Needed to Play: Core book, any even-numbered dice in any combination
Due to the nature of the dice resolution system, you can use any even-numbered dice you own in any mixture or combination as you are looking for evens, not any particular target number.
A note on dice: The company does produce specialty Ubiquity Dice (video 1, video 2) very cheaply (usually less than $5) which makes this process even faster while reducing the number of dice you are required to roll. The set of 9 comes with three U1s (representing 1 die), 3 U2s (representing 2 dice) and 2 U3s(representing 3 dice). They dice, when rolled deliver results showing the number of successes you would have earned rolling normal dice.
Alternate Core book suggestion: If you have difficulty obtaining the Desolation rules, or want something with more of a human-centric, swashbuckling feel, you could go for Triple Ace Games Ubiquity powered All for One: Regime Diabolique and hit all of your requirements at a 1636 level of technology (inclusion of muskets and pistols), minus fantasy races (which you would find pretty easy to devise). The magic system works in similar fashion, but is even easier to use, if harder on characters to use in daily life. This game has also been released as a Savage Worlds product recently, but I do not think that Savage Worlds meets your requirements as well as Ubiquity does.