Is there somewhere to find the base form of each new verb as it's introduced?
Try: http://prirucka.ujc.cas.cz/ put your verb in the first search field and hit 'hledej'
Is the form "potřebuji" also used?
Yes. Though one would hear that quite rarely in real life.
It happened to me to hear it more often in the bohemian part of the Czech Republic. Was that just a coincidence?
Potrebujem chleb, why the -u ending?
first person singular (I need)
Potrebujem is Slovak first person plural, Czech first person plural is potřebujeme. (just potřebujem is Common Czech, nonstandard).
"Potrebujem" is first person singular, in Slovak.