You can definitely swear fealty as a king. You just have to make a kingdom in a de jure empire your primary title. So if you want to swear to Byzantium, the easiest way is to form Sicily. Swearing to the HRE is more difficult because it usually holds its de jure lands, and the reason you're swearing in the first place is probably to avoid having to fight the Empire.
Anyway, you can totally cheese the game by beginning wherever you want, amassing a bunch of territory, forming the Kingdom of Sicily, swearing to Byzantium, turning yourself Greek Orthodox and eventually making yourself Emperor. A good candidate is William the Bastard with a claim on France forged before his invasion of England is over. Invades England, claims France, Holy War/forges claims on Sicily and joins Byzantium. You can even stay Catholic... until after the Pope gives you permission to invade the HRE. After you've forged a claim on Byzantium, of course.