My old computer in which I had iTunes on is broken. So my question is, are there any other ways of updating an iPad without having iTunes? If not, are there any stores that will do it?
While iOS 5 does, indeed, support iTunesless software update, previous versions don't, which is your case.
Therefore I suggest you to go to any Apple Store, which will certainly help you with your issue, or try any other Apple Retailler.