For gag reflexes and aversions to toothpaste, buy the smallest and softest toothbrush you can find. Many people like to use a baby or toddler toothbrush. A smaller head is easier to control and less likely to make you gag. If you can't stand the brush texture you can use just about anything else like a rag or a Q-tip (or twig!) to do it, though a brush does a better job because its bristles get into crevices better than any other tool. Flossing is equally important as brushing because, obviously, nothing else will clean between your teeth.
Toothpaste contains soap, gentle abrasives, and a bit of flouride. None of these things are strictly necessary for oral health in adults. Therefore there is very little benefit to brushing with toothpaste than brushing with plain water. You can use baby or toddler toothpaste which do not foam or contain strong flavors if you like the fresh feeling toothpaste gives your mouth. Otherwise there is no benefit from toothpaste and you can avoid it altogether.
The benefit from tooth-brushing is scraping sticky plaque off your teeth and especially around your gum-line. Once plaque has hardened into tartar, it cannot be removed by brushing and must be scaled off with a special pick at the dentist. So if you only brush once a week or once a month it's no better than brushing never. Doing it every day is what provides the main benefits.
And if your problem is cavities, try to avoid sweet acidic things such as juice or pop. Everyone seems to understand that sweets can cause cavities but not many people outside the dental profession are aware that acid is the worse culprit at eroding enamel.
I'm a licenced dental assistant which is why I can tell you these things.