In reading your post, I started to salivate!
Based on a comment within one of your post it sounds like the help desk is you plus a team of four--"...When not in session, we have one person assigned to each four-hour HD shift. During session, we have four per shift."
Couple of staffing questions come to mind: What are the other three persons doing when not on the help desk...are they the ones going out to the customers?
I have seen many activities suggested: individual training, cross-training, documentation, etc.
This is one comment that bothers me for many reasons: "But I also think it's unhealthy for the workplace to have staff sitting around browsing non work-related Internet sites, or just twiddling their thumbs during work hours."
Is there not an Internet or appropriate computer use policy for the state, your organization, etc. This is a starting point for turning the meaningless non-work-related surfing to something meaningful and productive for all.
Let's start with your group's charter. Does everyone have a documented position description that they understand? Are their goals documented? Are the goals measurable and achieveable? If the answer to any of these questions no...then you have one task for down time...update their professional goals. This gives you and your staff a basis of partnership for growth. It shows that you are in-tune with their professional development.
Pair a junior tech with a more senior tech for purposes of crosstraining. The young pups gain knowledge and they in turn can push the old dogs to learn new tricks.
I am a firm believer in standardization. Documentation, policies, and procedures are a must. With those things in place, they must be trained. Take inventory of these things. Update them and create them where necessary. Excellent skill builder. People get to develop their technical writing skills. They also learn what I call the zoom technique--seeing the big picture with an eye for detail.
What are your most and least common trouble tickets? If you cannot answer that with a quantitative answer, then sounds like a metrics project is in order. Knowing the hotspots can lead to planning, documentation, and training opportunities. It helps to post current tasks and progress in a visible area. As the task list gets larger and accomplishments are higher, the chart should move to a more prominent and visible location. Staff gets to see the gains. More importantly management sees it and your staff is aware of it!
Someone mentioned training? Building your own internal documentation library is good training with benefits. Developing the skill to keep it updated is another. Now take all the information that you amass and feed your users. Do you have someone on your staff with the gift of gab...then there is your brown bag lunch training specialist. Sell management with the idea of mini-training sessions for users once a month. Sessions are conducted by your staff.
As for training materials, organize the non-work-related activities into a quest to find training materials. Much of the certification material makes for good training material.
Proficiency skill drills are key to making sure everyone knows how to handle various situations using a structured method.
In your next staff meeting, be upfront with everyone. My opening comment would be: "You all enjoying the out-of-session rush? Good! Well we need to make better use of this time. I have noticed instances of Internet activities which are not related to work! I need your help to help me sell the idea of training so we can keep our skills sharp and expand them!" Show and sell the benefit!
Here is my favorite. I get hit with a question in a department head meeting that is technical support (I do security support). I assign the research issue to one of my staff. When I get that look of why us, I sell the idea that knowledge is power...My team has always expanded where other departments shrink. Impart critical thinking survival skills.
Pardon me for being all over the place. But I love to turn my down time into something of benefit. Mmmmm...every intern that comes to the project wants to be part of my team.