I tried small bicycle's tires and they were too hard for fitting. Is there anything that can be done?
This thing- http://www.instructables.com/id/How-to-make-custom-and-strong-tank-tracks-for-very/
is good but takes hell lot of time which I can't waste.
The only option remains is using cycle's tire after trimming them. I dont know why they have put simple rubber robot tracks at so high rates of about 1000$ for two 
Have you built a treaded robot before? Maybe I can take it's idea.