When a sentence starts with, "however", what part of speech is that? An adverb?

Yes, it is an adverb.

It is called a connective adverb in examples such as "That is probably true. However, we should consider some alternatives".

Or a relative adverb, as in "It's certain to go wrong, however we do it".

Or just a plain adverb when modifying an adjective, as in "He'll still get beaten, however powerful he is".

Is that what you wanted to know?

PaulM