Just to be sure I have this right - you want to insulate the wall abuting the house, i.e keeping the garage/workshop itself cold and outside the thermal envelope? You might want to insulate the workshop outside wall to some degree as well to make it more comfortable to use.
What U-value are the walls in the rest of the building? Do you propose to significantly increase those in the future? In general you want this wall to be at least as good as the others, including future improvements, although the spec can be lowered a little if the outside wall of the garage is done too.
I'm just doing my garage/workshop and plan to put 100mm PIR insulation up which gives a U-value of just under 0.2 (with no battens) which I think is an acceptable minimum spec. If you did both walls then something like 70mm on both walls could be OK.
Yes you do want a VCL, on the warm side of the insulation, so that's on the brick side on the internal wall, or inside the insulation on the external wall. The foil backing of insulation can provide this but it's not possible to tape the joints on the back surface so I'd put up a polythene sheet first, sealing the edges with orconF or similar non-setting airtightness adhesive.
As you probably want to put shelves up I'd choose something strong for the internal panelling. Various suggestions are given on this thread about this very subject:
http://www.greenbuildingforum.co.uk/newforum/comments.php?DiscussionID=8111&page=1#Item_7