OK, I've actually figured it out after looking at some tools available. I guess I can post my solution in case anyone ever encounters a similar problem:
1. Scale the whole spritesheet to your preferred size. GIMP is a good tool for that, I guess.
2. Cut the spritesheet into separate (smaller than original) sprites. I've done it with http://imagesplitter.net/ - it's pretty easy and fast to use.
3. Using the ImageMagick tool, make another spritesheet from the scaled sprites. The command for this would be something like:
montage *.png -tile XxY -geometry WIDTHxHEIGHT+XOFFSET+YOFFSET -background transparent NAME
Where: X is the number of columns, Y is the number of rows, WIDTH is the width of a new single sprite, HEIGHT is the height of a new single sprite, XOFFSET is half of the amount of pixels needed to make the new sprite match the original width, YOFFSET is half of the amount of pixels needed to make the new sprite match the original height and NAME is the name of the file of the new spritesheet. You calculate offsets with this formula: Offset = (OldSize - NewSize) / 2. For example, if your old size was 128/128px and after scaling it's 110/110px, you'd have to enter -geometry 110x110+9+9.
4. While you might be already done by this step, sometimes you may want to move the sprites a little (they will be centered and basically they will "start" a little higher, so unless you're making a top-down game, the sprites will probably appear to be floating in the air). Again, GIMP comes in handy: select the whole image and move it down a few pixels - that should do it.
