I'd go with rock climbing too, it'll depend on what is local to you how cheap it is but I was paying about £8 per session which for 2-3 hours of fun and exercise isn't that bad.
If you don't already then I'd suggest reading, it's not going to get you physically fit but it's cheap/free, informative, moving, provides escapism and requires very little time to do while potentially giving your mind a thorough workout (with the caveat that you are reading something weighty, with the best will in the World reading the Daily Star for instance is not likely to stretch your facilities too much).