Does the distribution of cards change every run?

Given that we don't know whether the game is changing the odds, and your sample size is far too small to conclusively prove anything about the probabilities of individual cards, knowing that there are a few dozen cards, and you only get around 40 chances at a card in a run, the probability of not seeing any card is actually reasonably high assuming the distribution is random.

That said, the game does have a fair amount of events and other things whose distribution is not entirely random. Let's create a list:

1. The shop.

The shop's card pool is smaller than the whole card pool. It also allows you a larger selection of cards, but costs gold.

2. Boss card pools.

Bosses always give you a choice between rarer cards.

3. Floor-based card pools.

The regular card pools include more improved cards on higher floors.

4. Specific events.

There are a lot of events that always give a particular type of card. Some of them are the only source of that card. There are also some that give a particular rarity; like the whale at the start of the game that can give you a 'rare' card.

5. Unlocks

You unlock new cards as you complete runs. This can change the distribution of cards and thus what strategies are most succesful, as the new cards may push one archetype or the other. Only applicable if you have not played a lot before, as eventually you have unlocked everything and no changes happen anymore.

Update: Exact card chances

Cards are drawn from 6 piles of each type of rarity and upgrade state. Each pile has an equal chance of putting out any card of that category, independent of how many you have already pulled out.

Each card drawn always has a 37% chance of being an uncommon. The chance of being a rare starts at 0%, and is improved by 1% with each common card drawn after the 2^nd, then tripled if you have nloth's gift. Also consult the following table. The 'avg' row is the result of estimating the average chance using a program that draws 1M cards.

+---------+-------------+------------+---------------+
| Commons | Rare(fight) | Rare(shop) | Rare (nloth)  |
+---------+-------------+------------+---------------+
| 0       | 0%          | 4%         | 0%            |
| 1       | 0%          | 5%         | 0%            |
| 2       | 0%          | 6%         | 0%            |
| 3       | 1%          | 7%         | 3%            |
| 4       | 2%          | 8%         | 6%            |
| +1      | +1%         | +1%        | +3%           |
| avg     | 5.0%        | 8.6%       | 7.5%          |
+---------+-------------+------------+---------------+

For example, if your first selection contained three commons, on your second selection from 3 cards you would have a 1 - (0.99 * 0.9837 * 0.9774) ~ 4.81% chance of seeing at least 1 rare card.

The chance of getting upgraded cards is dependent on the Act# and ascension:

+-----+----------------+-----------------+
| Act | Ascension < 12 | Ascension >= 12 |
+-----+----------------+-----------------+
| 1   | 0%             | 0%              |
| 2   | 25%            | 12.5%           |
| 3   | 50%            | 25%             |
+-----+----------------+-----------------+ 

Bosses always give you a choice between 3 rare cards.

Stores are even more specific: They always have 3 attacks, 2 skills, then 1 power (again which ones specifically is randomized), then 2 random colourless cards. The chance for cards from the store to be rare is much higher.

Code for the simulation below (C#)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace stsprob
{
    class Program
    {
        static void Main(string[] args)
        {
            Random R = new Random();
            Double s = 0.04;
            Double f = -0.02;
            Double n = -0.06;
            Double cs = 0;
            Double cf = 0;
            Double cn = 0;
            for (Int32 i = 0; i < 1000000; ++i) {
                double p = R.NextDouble();
                if (p < s)
                {
                    cs++;
                    s = 0.04;
                }
                else if(p < 0.63) {
                    s += 0.01;
                }
                if (p < f)
                {
                    cf++;
                    f = -0.02;
                }
            else if (p < 0.63)
            {
                    f += 0.01;
                }
                if (p < n)
                {
                    cn++;
                    n = -0.06;
                }
            else if (p < 0.63)
            {
                    n += 0.03;
                }
            }
            System.Console.WriteLine("Store estimate: " + (cs / 10000).ToString() + "%\r\n");
            System.Console.WriteLine("Fight estimate: " + (cf / 10000).ToString() + "%\r\n");
            System.Console.WriteLine("Fight(nloth's gift) estimate: " + (cn / 10000).ToString() + "%\r\n");
            System.Console.ReadLine();
        }
    }
}