Adding "half-pixel" is helping when its not zoomed-out. I guess i can tie it up to zooming, but still, this is not perfect solution.
If it's a precision problem then rounding correctly won't help. Even though i tried rounding all up, rounding all down, and rounding some down and some up it did not help.
The problem is probably in the non-perfect representation of numbers by the float type.
For the record, this is the way i round down:
quad[0].texCoords = sf::Vector2f(floor((float)tu * 64 + Fraction), floor((float)tv * 64 + Fraction));
quad[1].texCoords = sf::Vector2f(floor((float)(tu + 1) * 64 - Fraction), floor((float)tv * 64 + Fraction));
quad[2].texCoords = sf::Vector2f(floor((float)(tu + 1) * 64 - Fraction), floor((float)(tv + 1) * 64 - Fraction));
quad[3].texCoords = sf::Vector2f(floor((float)tu * 64 + Fraction), floor((float)(tv + 1) * 64 - Fraction));