> How would a company even determine if I'm worth hiring
  > and going through all the work to get me a work visa
  > if they can't even interview me in person?

No company will hire you without an in-person interview. Most companies will pay for your plane tickets and hotel for an in-person interview.

A note on in-person interviews:

You will probably be flown to Europe and do the interview in English. Most English speakers in Europe learned it as a second language. If you learned English from a local Somali school, your interviewers will not be used to your accent and may have a hard time understanding you. You should practice your accent until you sound close to British or American.

  > Would they tolerate my crappy internet if they try to
  > interview me over Skype?

Is your connection good enough to do a voice call at high quality? If it is, that should be sufficient.

Otherwise, you'll need to find a way to skip the initial phone interview. Most software companies do phone interviews to screen out candidates who are not capable of programming. A good substitute is a portfolio of personal projects on GitHub, showing experience with the programming languages you put on your resume.

  > What if the position was for something mid-to-entry
  > level and not some key position.

This will depend on the size of the company. I work at Google, and the legal department here will handle the immigration, visa, and permanent resident process even for regular low-level engineers. Smaller companies will be more selective.