All the addresses I can see starts with '1' which means legacy addresses and now everything is about moving to a SegWit address.
I found some hints on reddit but I'm not 100% sure if they are OK, so please let me know if you know a reliable SegWit address generator which is offline and which is not a scam.
Basicaly what needs to be done is the following: you need to be generating random private keys, from them you need to be calculating the public addresses and if the prefix of the address matches your string - voila!
The longer the required prefix, the longer it takes to find a match.
If I don't want to send any coins to the new address before I check if the key and the address works, is it possible to check the private key with signing a message? I assume I have to check it with an airgapped PC. So I mean that I prepare a message on an Internet enabled PC, and transfer it with a USB drive to the airgapped PC, sign it, and try to check the signature on the internet enabled PC?
Or, it's easier to send 0.000001 bitcoin to the address, and try to spend it with nearly 0 fees? (e.g. 1 sat/B)
Additionally, you need to put the code inside a loop. You would be generating randomly private keys in a loop until the corresponding public key matches your desired prefix.
The code in the link provided works for legacy addresses. It is surprisingly difficult to find the corresponding information on SegWit addresses. I will try to find a link for you and update that post.
As you can see, the DIY approach has the code which is very simple and straightforward, it is by no means rocket science, and the advantage over using some publicly available third-party software or online service is that you are 100% sure you are on a safe side.
To reverify that the private key is really good for your public address before you send your founds there, you can use https://www.bitaddress.org/ service, but make sure you bring your computer offline to do that (again, to be on a safe side)