I self taught myself how to do Excel. Also we have what I believe is called an SMS network system at work. Whatever the heck it’s called, I taught myself how to create menus and tiolr reports.
We’ve always had computers at work. We just didn’t have the internet on them.
I read books. Lots and lots of books.
I didn’t do anything, at least for a few minutes. It gets boring quick, so I’d look for, or create, more work to do. You can almost always find something. If you can’t find anything, you’re probably on the verge of getting laid off. I wouldn’t want to go back to those days, but I must say I was a lot more productive.
My career has been almost entirely surrounded by or involved with computers in some way or other. Early in my career I programmed greenscreen apps in COBOL. There really wasn’t ever much downtime, because whenever for some reason I was in a holding pattern on my primary assignment, there would always be some collateral project I needed to work on. When I frst transitioned into IT, I was still officially a subject indexer and had indexing work to do alongside. I should point out that this period in my career was spent in small companies which did everything that needed to be done, themselves.
Later I was at a huge pay TV company where minute division of labor and outsourcing were the hallmarks. When it isn’t possible to get anything done without getting Denver, Manila, and Bangalore on a conference call, you’re more apt to find yourself in an idle situation. Especially if if it’s the sort of company where you get called on the carpet for approaching the wrong people with a question. Some people can thrive in that kind of environment, but they are generally not the traditionally stereotypical computer geeks. Those people can fail miserably. So I’m told, but of course I wouldn’t know anything about that.
Read and/or get my work area ready for the next job.
Being an Australian we did the usual:
Poetry readings.
Heats of the formal debating series.
Sensitivity training exercises.
Yoga.
Bible reading groups.
Before computers and the Internet? I played outside at recess. 
I’ve used a computer of some sort since I was 7.
I grew up with computers, but in those situations whether at work or more often in school when I didn’t have access to a computer and I had down time, I would DRAW. I drew in class constantly. I did a lot of my best drawings during class. Sometimes the teachers would see them and, instead of reprimanding me, actually be so impressed by what I drew that they would take it and show it off to the class, apparently unconcerned that I hadn’t been paying attention. (And I’m talking about college classes here.)
That’s weird. The OP’s scenario is unheard of in the Netherlands.
At most white collar jobs in the Netherlands, when there isn’t any work to do, (which is hardly ever the case, somehow) you ask your supervisor if there’s anything to do. If he can’t think of anything, then you go home. People seldomly kill time on their jobs. maybe they will surf a little if they are taking a short break, but otherwise? No.
My very first job was at a Tarot hotline - I basically sat in a cubicle doing tarot readings over the phone. We didn’t have any computer, just phones. My colleagues were all women, mostly New Age crystal-toting Reiki healers and some Goths. Downtime was spent:
I hated that job, but it gave me some good stories. Like a colleague walking past my cubicle and exclaiming “Are you okay? Your aura is all purple!”.
I’ve had jobs where there were no coworkers I could talk to, during most of my downtimes. So I’d read, study or stretch.
I only really had one job that had so much downtime that this was an issue and was pre-internet (or, at least, the internet existed but the company didn’t allow people to have access to it) and I was specifically forbidden by my section head to offer to help other sections because it made us look like we weren’t busy (idiot).
In this job I taught myself how to use the various microsoft packages to a much higher level of competency by trying to make up reasons to use them in my job (although this slightly backfired by making my job even more automated and even less time consuming in the long run - doh!). I also wrote a novel too, but it was basically little more than a writing practice exercise, the plot was paper thin and all the characters were named after people from the company. Unsurprisingly it was a smash hit with my colleagues who were always waiting for the next instalment as they got to read about themselves 
When I didn’t feel like doing any of that I wandered around and talked to people, although not too much as that was kind of frowned on.
Where do you work? What is your job? Are there any openings? Can I telecommute?
SkiFree.
I used to wander around and gossip, mostly in the kitchen at work. We didn’t have water coolers but we had one of those giant coffee makers - urns I think they’re called.
We’d also photocopy the crossword and have a group puzzle solve event.
Flirt, I forgot flirt. Those were some fun times.
I taught myself to draw. I’m proudest of this pine tree I drew and framed it in front of my Quality Training certificate (after I left the job).
I also played word games with a couple coworkers. Things like, What else do the company’s initials stand for. We also amused ourselves writing top 10 lists.
When I worked at a job where internet, though technically available, was strictly forbidden (and they checked the logs), I killed time using MSPaint to create abstract “art”. Eventually I gave up even that semblance of trying to look busy and just brought books to read.
It’s been a long time since I was working at that type of job. I’ve been self-employed as an Audio/Video/Computer type person for quite a long time. But I did six months on a contract for Lucent in the late 90s. The project I was working on got canceled one month after they renewed my three month contract, so I literally had nothing to do for two whole months. I had web access, but they logged all visits. Luckily I had a shell account at my ISP, and am grizzled enough to know all the text-based tools to read e-mail, newsgroups and the web.
Before that, I did 3D modeling and animation in the mid 80s to early 90s, and there was little Internet around. But as we were working with very slow computers and rendering an animation test or even a sufficiently complex single frame, I’d go off on what my boss called “render wanders”.