There is an assumption behind the quantity theory of money that the velocity of money remains constant, which I believe is true only for short runs, then why does the theory of inflation, which is %(change in price) = %(change in Money supply) - %(change in aggregate output), valid for long run? Moreover, the quantity of theory of money also assumes that there is full employment, so doesn't this imply that the change in aggregate output should be zero as it is always the maximum possible?
Actually velocity of money was never assumed by serious economists to be constant in short-run. I don't believe there is any source that would make such assumption. It was always assumed by monetarists such as Friedman to be constant in long-run.
Empirically velocity of money in US was constant in long run for very long period of time, but not in recent decades. As you see from the data below provided by Fed the velocity of money was roughly around 1.6-1.7 on average between late 50s and early 90s with only relatively small amount of variation around the trend. This remarkable stability of the series would justify the assumption of velocity of money being constant in long-run. However, note if you zoom in on each decade there is short-run variation, so no serious economist would argue it was constant in short-run. Similar trend was observed in other developed countries, I believe Japan was notable example of a country where velocity of money had very obvious declining trend in long-run.
However, ever since early 90s we see that velocity of money in US became unstable as the data show. Hence, presently the assumption that velocity of money is constant in long-run is not really justifiable anymore.