Now, keep in mind these wouldn't be gyms in the traditional sense. The "Gyms" would be large areas, mainly in big cities or other large areas, that would offer training in specific skills, for a price. For example, an Archery Gym wouldn't be a closed off building, but an outdoor area with free equipment availible (provided it stays on site) and targets set up at different ranges. Now, in a Gym, usage of the specified skill would increase it's level faster than normal, but only by using the equipment in the Gym. For example, you would need to hit the targets in the Archery Gym to advance the skill, and each would give a locked amount of progress towards increasing it to prevent boosting.
This wouldn't work for all skills, naturally, but would provide a nice substitute to the instant-train teachers in Oblivion. You would pay to get in a gym, and that payment would last for a set amount of time before expiring. Gyms could work for skills such as:
Unarmed-Beat up punching bags and even spar with other members
Blade/Blunt-Use wooden versions of weapons to spar, and whack training dummies silly
Block-You step into a batting-cage style area, where objects are lobbed at you, and you must block them
Archery-Practice on targets using the bows and ammo available.