Q:

How can we feel temperature?

Recently I watched a Youtube Video by
Veritasium
He said we are actually feeling the rate of heat transfer, not the temperature.
But how do we feel temperature?
How is temperature different from heat and heat tranfer?

A:

The answer to "How do we feel temperature" is "you define temperature in a way that is different from how physicists define it."  This video does an excellent job of showing the issue off.
In science, temperature is defined to be a measure of the energy of highly disorganized motion of atoms in a material.  In everything around you there is motion of this sort -- quite a lot of it in fact.  You can't see it because its all disorganized.  If one molecule in the key of your keyboard is vibrating towards you, its highly likely that the molecule next to it is vibrating away, so you don't notice the motion.  However, everything is moving in this way.
We observe that if you put two objects together, they can transfer energy in this way.  This transfer of thermal energy from a "hot" object to a "cold" object is called "heat" (another word which has a very specific meaning to physicists which is more picky than our day-to-day-usage).  Two objects are defined to be of the same temperature if, when you put them together, no thermal energy transfers from one to the other.
If we want to look at how fast that heat transfer occurs, we need to look at more than just the temperature of the object.  Temperature does play the expected part (large temperature differences mean you transfer more heat!), but the material properties also matter.  Metals, for instance, are very good conductors of heat.  If you have a warm piece of metal and you touch it, it transfers heat very quicky.  On the other hand, if you have an insulator of heat (such as a down jacket), it will transfer that heat slower.  Rest assured, though, by the laws of thermodynamics, both materials will eventually reach the same temperature as their surroundings, but the metals will do it faster.
We do actually measure temperatures, and rates of change in tmperature, but we measure them within our skin, and those temperatures measured are not just a simple measurement of the object, but are a complex balance between our body's internal temperature and the object.
For example, typically the body's core is 98.6F, but the skin is typically closer to 91F.  Why?  It's because we're constantly emitting heat into the air (which is colder).  If we touch a piece of metal at the same temperature as the air, however, we feel as though it is "colder."  Why?  Because the metal can pull heat away from the body faster than the air, so the skin temperature will be lower than it was in the air.  The metal will feel colder, even though it, in fact, has the same temperature as the air!  Because of this dynamic effect, it's typically more precise to say that we sense heat transfer to/from an object more than we sense its actual temperature.  The sensations you and I grew up to think of as "hot" and "cold" are really more "fast influx of heat" and "fast outflow of heat."
As for how we actually sense that temperature, that is a question for Biology.SE.  However, there's a few pieces worth mentioning:

We have proteins that deform slightly at a given temperature.  These are used to tell us if an object is hot or cold (and by that I mean tell us that the skin has been made hotter or colder).  TrpV1, for instance, deforms to let ions pass through it at 43C/109F.  Capsaicin, the active ingredient in spicy food and pepper spray, also deforms TrpV1, which is why you feel like your mouth is burning.
Our brains are amazing signal processors, so its easy to get the illusion that they are measuring something they aren't.  For example, the sensation of burning is currently believed to come from measuring heat-transfer by watching the signals from the different layers of skin and effectively calculating a heat flux from that.  This is why you still feel burning after your fingers have left the hot object.
Our slowest moving temperature sensors are used in homeostasis.  There, we contrast reactions which move at different speeds at different temperatures to figure out what our actual temperature is.

A:

In a few words, temperature is a macroscopic property related to the kinetic energy of molecules. 
What it really is, is a tricky question, because we don't know what mass is or what force is, but we know how to measure and relate each other and how to intuitively understand. Based on that, we can infer some key properties about temperature.
First of all, it is important to understand the difference between heat and temperature. Heat is energy, and when we are dealing with thermal systems, heat depends on the amount of mass that contains that energy. We call that an extensive property. (more about that). You would imagine that heating a house would take a lot more energy than to heat a can of water, for example.
Temperature, on the other side, is an intensive property, i.e. it does not depends on the size of things. A 30ºC house wouldn't be hotter than a 30ºC water in a can. So, temperature is kind of an index, it is a metrics associated with each point in space. 
Heat transfer is related to heat flux. And heat flux as the name says, measures how much heat is flowing from one place to another.
When we are dealing with steady-state systems (https://en.wikipedia.org/wiki/Steady_state), we can assume that:
$$\Delta T=\dot{Q}\frac{L}{kA}$$
Explaining this equation: If we have a wall with two sides, the difference of temperature $\Delta T$ between the two sides will be proportional to how much of heat is coming in and out ($\dot{Q}$) and to the thickness of the wall ($L$) and inversely proportional to the conductivity ($k$) and area of the wall($A$). We often think the term $\frac{L}{kA}$ as thermal resistance as it is analogous to the equation in electricity:
$$V=RI$$
If you are familiar, $V$ is the difference of potential (analogous to $\Delta T$), $I$ is the current (analogous to how much comes in and out, $\dot{Q}$) and $R$ would be the resistance, as I pointed. As in electricity, $V$ is a point property (it depends on two points) and $I$ is the flow of electrons.
These points were just to make clear the distinction between these properties. But then, what is really temperature all about? 
Well, temperature is an useful measure to know thermal characteristics of a system. 

We know that the dilation is proportional to temperature. Based on that, we have built thermometers, which use the principle of dilation.
We know that two bodies in contact with each other will empirically have the same temperature at infinite time. 
We understand that thermal equilibrium, i.e. when two bodies exchange no energy, occurs when the temperature of both are the same.
In the perfect gas model, empirically discovered, we know that $PV=mRT$, i.e. four measurable properties (pressure, volume, mass and temperature) have a relation within a range of values.

