Most of GM:ing is just playing out
various characters and I'm rather weak at making them up on the fly
and too lazy to prep for it. Thus to improve, something has to change.

First I tried, with surprisingly good result, using a deck of
girly wiccan tarot cards. Instead of plain tarots these had the
meanings actually written on the cards. Then, when a npc was needed
I would just pull few cards and scrape inspiration of them.

Works, and fortune tellers do this all the time.

Though it mandated carrying a girly tarot deck and coping with
things like drawing "Final trust" and  "Obedience" and ending up with
too much comic factor. And of course, I forgot the NPC:s two minutes
after they left the scene.

Thus, I thought, I use computer for pretty much anything, why not just
make ready printouts with names and some traits and go from there?
Character is already written down so no time wasted doing that in middle
of the play.

After fiddling afternoon or two I had a bit of code that prints out 2in x 3in cards with
name on the top and traits and skills below. This turned out to be
quite disapointing. Why? Game starts, five minutes pass with lot of action.
Then someone asks "Do we have a good archer on our ship?". Then 10 minutes
pass with no action as I scan my deck of characters and read them
all through..

A Failure. Couldn't improvise, was stuck with what I had instead of
having players be stuck with whom they have on board their ship.

Lessons learned:
* Keep room for improvised characters.
* It is Not ok to make 45 random characters for one session.
* Sort by skill to aid in finding experts quickly
* Too much information is not good.
* There is a distinctive difference of having a character in your head
  than on the paper.
* It would be good idea to read characters through before starting
* Card is very bad form factor since you have to avoid sneezing if you
  cut them out of ordinary paper. List would be easier to scan through.

Oh, and your totally random npc of day:

-= Herbertus(m) =-
Persona:      Wise, in love.
Appearance:    Round face, stained lips.
Desires:      Passion, love
-----------------
Skills:        Leatherworking: Good, Wagoneering: Good, Geography: Poor
Stats:        Physical: Good, Self-Control: Mediocre, Charisma: Poor

Perhaps still too much info to handle on the table though.. What should
I add to make these come to life? The texts from the girly tarots(tm)? Perhaps
tarots work better for their fortune telling aspect of not actually saying anything
but inspiring?

Welcome to the Forge.
Most people use their real name here.

As for your problem, I think you have too much linked info there.
You pretty much know the high skill character should have from the context ("Is there an archer here?" kind of demands someone with talent at archery, for example).
So, have a list of names, and a separate list of features. These can be anything from skills to personality to odd habits.
When an NPC is needed, pick (or roll) a name and a feature. Add everything else on the fly as required by the situation.
For extra inspiration, take another feature.

You might want to separate skills and other stuff, depending on the system in use.