What came first, transaction or mining?
Mining was first, as you say, there had to be bitcoins to transact which must have come from mining blocks. The key is, that blocks can be empty. Most early blocks were. And even some blocks now are mined empty, e.g. this one: https://blockchain.info/block/0000000000000000005afd87cdbb34e8126674766c261619044c4c213286d72b

Blocks always contain a Coinbase transaction which pays the reward to the miner regardless of whether there are any other transactions to mine or not.

The incentive for miners to include other transactions in blocks rather than leave them empty is the transaction fees.