You can surely insulate the walls with no problems, then finish them off with drywall or whatever, if you wish.
As for the ceiling, you can have insulation up there between the ceiling joists, and still store stuff on top of the ceiling joists. For example, if you have 2x8 ceiling joists, you can have 7 1/4" of insulation up there. If you finish the ceiling with sheetrock or some other material, you could blow in cellulose above it.
You would need some way to access the area, like one of those pull-down staircases which one sees from time to time.
You would want to vent the attic first.
7 1/4" of cellulose is not much, but it will certainly help if you are planning on heating up the space while you are working there during the day.
I have a garage workshop which is insulated to about these same standards (r-13 in the walls and something minimum in the attic) and it has only been down to 36 F in there so far, and we have had lows down to about zero.
My workshop is about 16x20 and I have a furnace which I believe is 75,000 btu. I have no plenum on the furnace and just a filter in front of the hole where there should be a filter rack.
I can turn that furnace on when I open the garage and it will go from say 40 degrees to 60 in about as much time as I can bring my lunch bucket from my car.