Can I use trademarked logos on product I am selling to the Trademark owner or a division thereof?

A two part question for my startup:

I intend to sell products / stationary (such as letterhead, pencils, pens, etc.) to companies (or divisions of a company). Would it be illegal to create samples using their trademarked logo (strictly for their preview)?

If the company (or a division of the company) agrees to ordering a batch of these products, would I need to bother obtaining a license to the trademarked logo? Or would that not be necessary?

It would not be illegal. A trademark does not prevent you from using the mark, it prevents you from using it in trade in a manner which is confusing.

For example, the fact that Coca Cola owns this trademark:

... does not legally mean I can't use it here in this answer. It just means I can't use it in trade, that is, I can't use it to sell some other soft drink. I can't use it in a way which would confuse people as to the origin of goods.

So let's say you make a bunch of Coca-Cola logo pencils. If you try to sell them, somebody might be rightly confused that you represent Coca-Cola. This is a trademark infringement. But suppose you make a movie called The Coca-Cola Kid. (This was a real movie). Because it's a movie and because there's no chance that any sane person would think that the movie was a product of The Coca-Cola Company, it is not an infringement.

In the case you're describing, making a sample of a promotional item which you are giving away for free to the trademark owner, there's no infringement. This practice is commonplace. Look at the websites of any of the promotional item vendors (such as epromos.com) and you'll see zillions of products bearing trademarks. When they show a AAA mug nobody thinks that they are AAA and there is no possibility of consumer confusion, nor are they trading on AAA's good name and reputation, so there is no infringement.

Most large companies do have internal policies for trademark usage which they will expect vendors to comply with as a condition of doing business. For example I'm sure that Coke is very concerned about the exact shade of red and it would drive them crazy if you had a lavender Coke logo. They usually have large books of instructions on how to use their logo which they'll give you if they hire you to make promotional products.

(I am not a lawyer and this answer confers no rights).

I intend to sell products / stationary (such as letterheads, pencils,
pens, etc.) for companies (or divisions of a company). Would it be
illegal to create SAMPLES using their trademarked logo (strictly for
their preview)?

It depends on how the owner of the trademark views this since the owner is the one that would take action against you for infringement. You should ask the owning company first.

If the company (or division of the company) agrees to ordering a batch
of these products, would I need to bother obtaining a license to the
trademarked logo? Or would that not be necessary.

If they've already agreed to ordering a batch of these products, then they should be fine with licensing the mark solely for the production internal consumption goods. Part of license may stipulate that you may not be allowed to sell such goods to an unauthorized party.