This is the case of the Crimson biome, but if you are in the Corruption in its stead, it is the same path of action, since apart from the appearance and name, the blocks' properties don't change.
In the same fashion of this question, you can't mine Crimstone Block prior of making a fifth tier pickaxe, for example Deathbringer pickaxe (Nightmare pickaxe for the Corruption biomes).
Thus you're right in saying that you need Tissue Sample, which is looted on the Brain of Ctlulhu. (Or Shadow Scale from Eater of Worlds in the Corruption.)
So, in order to progress, you'll have to break the Crimson Hearts (Shadow Orbs in the Corruption). Since you can't mine the Crimstone Blocks yet, you'll have to either use Purification powder from the Dryad on the blocks in your way to mine them, or use explosives like Bombs from pots or the Demolitionist which will blow them up; then you can destroy the Hearts/Orbs with a hammer or explosives.
Then you'll be able to craft the fifth tier pickaxe and progress in the game.