Change visa/city tax proof

I moved from the countryside to the city in March for a new job.
I should have changed my visa status back then (oops).
The paperwork says I need proof that I paid my city tax from the countryside.
Does that mean city tax from LAST year?
Or THIS year? Because the last city tax isn't due until January 2019.
If it's THIS year, that means I have to pay the last city tax early?
And THEN request proof?

You simply need to get the records showing what tax you paid from the previous city office. I do this each year and is pretty straight forward.
You don't have to pay the full year if you don't live there the full year. My local city is pretty good at adjusting and refunding over payments (which happens from time to time).

"You don't have to pay the full year if you don't live there the full year."
it is incorrect.
no adjustment system between cities.
of course, no refund.

you moved from city A to city B
city tax: 2018's city tax is calculated, based on 2017's income. it should be paid from June,2018 to July, 2019, if it is withheld from your annual salary. ( you have to pay city tax at the place you lived on Jan. 2018)
you moved in March 2018. I think you have received pay strips from city A in May (or June) 2018. you have to pay a full amount of 2018's city tax of city A until the deadlines.
if you are talking about 納税証明書, an example is like that.
http://www.city.osaka.lg.jp/zaisei/cmsfiles/contents/0000071/71318/201...
if you have unpaid tax, it will be shown in 未納額 column.