Sachverhalt:
A.
A._ (geb. 1986), kosovarischer Staatsangehöriger, reiste am 14. März 2011 unter seinem damaligen Namen X._ illegal in die Schweiz ein, worauf er am 23. März 2011 in den Kosovo zurückgeführt und mit einem Einreiseverbot bis 22. März 2013 belegt wurde. Nachdem er seinen Namen X._ in A._ hatte ändern lassen, reiste A._ am 14. Juli 2011 wiederum illegal in die Schweiz ein. Die Rückführung in den Kosovo erfolgte am 19. Juli 2013. Am 4. September 2013 wurde erneut ein Einreiseverbot ausgesprochen, gültig bis zum 3. September 2015.
Am 6. März 2015 heiratete A._ die Schweizerin B._ (geb. 1994). Diese stellte am 20. Mai 2015 ein Familiennachzugsgesuch für A._. Die Gatten wurden am 27. Juli 2015 getrennt befragt. Trotz vorhandener Indizien konnte eine Scheinehe nicht nachgewiesen werden, weshalb das Familiennachzugsgesuch am 29. Oktober 2015 bewilligt und A._ am 18. November 2015 die Aufenthaltsbewilligung mit Gültigkeit bis 31. Oktober 2016 erteilt wurde.
B.

Am 4. März 2016 teilte das Migrationsamt des Kantons Solothurn A._ mit, es werde der Widerruf der Aufenthaltsbewilligung wegen Eingehens einer Scheinehe in Erwägung gezogen, und gewährte ihm das rechtliche Gehör. A._ und B._ bestritten in ihrer Stellungnahme vom 15. März 2016, die Ehe nur zum Schein geschlossen zu haben. Am 26. April 2016 widerrief das Departement des Innern des Kantons Solothurn die Aufenthaltsbewilligung und wies A._ aus der Schweiz weg. Die von A._ und B._ dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 4. Oktober 2016 ab.
C.
A._ und B._ erheben am 4. November 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit den Anträgen, das angefochtene Urteil aufzuheben, vom Widerruf der Aufenthaltsbewilligung abzusehen und auf jegliche Wegweisungvollzugs- und Fernhaltemassnahmen zu verzichten. Eventuell sei das Verfahren zur Neubeurteilung an das Verwaltungsgericht zurückzuweisen. Subeventuell seien die Unzulässigkeit und Unzumutbarkeit des Wegweisungsvollzugs festzustellen und das Migrationsamt sei anzuweisen, dem Staatssekretariat für Migration zu beantragen, A._ die vorläufige Aufnahme zu erteilen. Zudem wird um Gewährung der unentgeltlichen Prozessführung mit Advokat Dieter Roth als Rechtsbeistand ersucht.
Das Verwaltungsgericht und das Departement des Innern schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Staatssekretariat für Migration hat auf Vernehmlassung verzichtet.
Am 7. November 2016 ist der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt worden.
D.
Am 9. November 2016 wurden A._ und B._ aufgefordert, bis am 1. Dezember 2016 einen Kostenvorschuss von Fr. 2'000.-- zu bezahlen oder innert der gleichen Frist den Bedürftigkeitsnachweis für die unentgeltliche Rechtspflege vorzulegen. Der Kostenvorschuss wurde am 28. November 2016 bezahlt. A._ und B._ reichten am 12. Januar 2017, zusammen mit ihrer Replik, den Erhebungsbogen für die unentgeltliche Rechtspflege mit Nachweisen zur wirtschaftlichen Situation ein.
Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten betreffend den Widerruf oder die Nichtverlängerung der Aufenthaltsbewilligung des ausländischen Ehegatten einer Schweizer Bürgerin ist zulässig (<ref-law> e contrario i.V.m. Art. 42 Abs. 1 AuG [SR 142.20]). Der Antrag betreffend Wegweisung ist im Rahmen der Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht zulässig (<ref-law>). Er kann auch nicht als subsidiäre Verfassungsbeschwerde gemäss <ref-law> entgegengenommen werden, da keine entsprechenden Verfassungsrügen erhoben werden (vgl. <ref-law>). Auf den Antrag betreffend Wegweisung ist nicht einzutreten. Auf den Antrag betreffend Verzicht auf Fernhaltemassnahmen ist ebenfalls nicht einzutreten, weil diesbezüglich kein anfechtbarer Entscheid vorliegt. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten dagegen wäre zudem unzulässig (Art. 83 lit. c Ziff. 1 AuG).
1.2. Die Beschwerdeführer sind als Ehegatten zur Erhebung des Rechtsmittels legitimiert (<ref-law>). Auf die Beschwerde ist einzutreten, soweit damit sinngemäss die Verlängerung der (inzwischen abgelaufenen) Aufenthaltsbewilligung des Beschwerdeführers 1 beantragt wird.
2.
2.1. Gemäss Art. 42 Abs. 1 AuG haben ausländische Ehegatten von Schweizerinnen und Schweizern Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen. Die Ansprüche nach Art. 42 AuG erlöschen, wenn sie rechtsmissbräuchlich geltend gemacht werden, namentlich um Vorschriften dieses Gesetzes und seiner Ausführungsbestimmungen über die Zulassung und den Aufenthalt zu umgehen (Art. 51 Abs. 1 lit. a AuG).
2.2. Ob eine Scheinehe geschlossen wurde bzw. ob die Ehe bloss noch formell besteht, entzieht sich in der Regel dem direkten Beweis und kann nur durch Indizien erstellt werden (<ref-ruling> E. 4.2 S. 9 f.; <ref-ruling> E. 10.2 S. 135). Solche Indizien können äussere Begebenheiten sein wie die Umstände des Kennenlernens, eine kurze Dauer der Bekanntschaft, eine drohende Wegweisung, das Fehlen einer Wohngemeinschaft, ein erheblicher Altersunterschied, Schwierigkeiten in der Kommunikation, fehlende Kenntnisse über den Ehepartner und dessen Familie oder die Bezahlung einer Entschädigung für die Heirat. Die Indizien können aber auch psychische Vorgänge betreffen (tatsächlicher Wille). In beiden Fällen handelt es sich um tatsächliche Feststellungen, welche das Bundesgericht nur auf offensichtliche Unrichtigkeit oder Rechtsverletzungen hin überprüft (<ref-law>; <ref-ruling> E. 2.3 S. 152). In die vorinstanzliche Beweiswürdigung greift es nur ein, wenn diese willkürlich ist (Urteile 2C_752/2016 vom 16. September 2016 E. 3.2; 2C_1141/2015 vom 18. Juli 2016 E. 2.2; zur Willkür in der Beweiswürdigung vgl. <ref-ruling> E. 4.4 S. 444; <ref-ruling> E. 4.2 S. 234; <ref-ruling> E. 4.2 S. 560). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe sei rechtsmissbräuchlich oder bezwecke die Umgehung fremdenpolizeilicher Vorschriften (<ref-ruling> E. 2.3 S. 152). Dass die Begründung einer wirklichen Lebensgemeinschaft gewollt war, ergibt sich nach der Rechtsprechung nicht notwendigerweise schon daraus, dass die Ehegatten während einer gewissen Zeit zusammengelebt und (angeblich) intime Beziehungen unterhalten haben; ein derartiges Verhalten kann auch nur vorgespiegelt sein, um die Behörden zu täuschen (<ref-ruling> E. 2b S. 295 mit Hinweisen; Urteil 2C_804/2013 vom 3. April 2014 E. 2.2).
2.3. Eine Scheinehe liegt umgekehrt nicht bereits dann vor, wenn auch ausländerrechtliche Motive den Eheschluss beeinflusst haben. Erforderlich ist, dass der Wille zur Führung der Lebensgemeinschaft im Sinn einer auf Dauer angelegten wirtschaftlichen, körperlichen und spirituellen Verbindung zumindest bei einem der Ehepartner fehlt (<ref-ruling> E. 3b S. 102). Grundsätzlich muss die Migrationsbehörde die Umgehungsehe nachweisen. Dass eine solche vorliegt, darf dabei nicht leichthin angenommen werden. Die Behörden müssen den Sachverhalt von Amtes wegen möglichst zuverlässig abklären; indessen wird der Untersuchungsgrundsatz durch die Mitwirkungspflicht der Parteien relativiert (vgl. Art. 90 AuG). Diese kommt naturgemäss bei Tatsachen zum Tragen, die eine Partei besser kennt als die Behörden und die ohne ihre Mitwirkung gar nicht oder nicht mit vertretbarem Aufwand erhoben werden können (<ref-ruling> E. 8.6.4 S. 496 f.). Das gilt insbesondere, wenn bereits gewichtige Hinweise für eine Scheinehe sprechen; dann wird von den Eheleuten erwartet, dass sie von sich aus Umstände vorbringen und belegen, um den echten Ehewillen glaubhaft zu machen (Urteile 2C_936/2016 vom 17. März 2017 E. 2.3; 2C_804/2013 vom 3. April 2014 E. 2.3).
3.
3.1. Daraus, dass die Migrationsbehörde in einem früheren Zeitpunkt zum Schluss gekommen ist, die Indizien würden für die Annahme einer Scheinehe nicht ausreichen, können die Beschwerdeführer nichts ableiten. Handelt es sich nämlich - wie vorliegend - um die Verlängerung einer abgelaufenen Bewilligung, gelangen nicht die Regeln über den Widerruf rechtskräftiger Bewilligungen zur Anwendung, sondern die Behörde kann aufgrund einer Gesamtwürdigung - unter Einbezug bereits früher bekannter und zusätzlicher neuer Erkenntnisse - das Vorliegen einer Scheinehe bejahen (Urteile 2C_459/2016 vom 12. Oktober 2016 E. 3.4.1; 2C_740/2015 / 2C_752/2015 vom 10. Februar 2016 E. 3.3; 2C_310/2014 vom 25. November 2014 E. 2.4.2; 2C_500/2011 vom 20. Dezember 2011 E. 2.5).
3.2. Die Beschwerdeführer gaben an, sich 2012 in einem Internet-Chat kennengelernt zu haben. Die Vorinstanz ging davon aus, dass sich die beiden nur schwer verständigen konnten, weil die Beschwerdeführerin 2 kaum Albanisch verstanden und der Beschwerdeführer 1 nur gebrochen Deutsch gesprochen habe. Eine Sprache "gebrochen" zu sprechen bedeutet, sich verständigen zu können, wenn auch mit eingeschränktem Wortschatz und ohne die Grammatik zu beherrschen. Für die Kommunikation in einer Partnerschaft kann es genügen, wenn ein Partner die Muttersprache des anderen versteht und - wenn auch nur gebrochen - spricht. Indessen gaben die Beschwerdeführer an, für die Verständigung den Übersetzungsdienst "Google Translator" zu benutzen. Vor diesem Hintergrund ist die Einschätzung der Vorinstanz, die Beschwerdeführer hätten kein flüssiges Gespräch führen können, nicht zu beanstanden. Die Beschwerdeführer wenden ein, Übersetzungshilfen sowie die Funktion "Copy paste" würden eine zügige und inhaltlich weitgehende Übersetzung ermöglichen, was durch die eingereichten Kurznachrichten (SMS) belegt sei. Dies ändert jedoch nichts daran, dass eine spontane Kommunikation auf diese Weise nicht möglich ist. Auch in einem "bildungsfernen Milieu", welchem die Beschwerdeführer ihrer Ansicht nach angehören, ist die sprachliche Kommunikation ein wesentlicher Teil der Interaktion. Der Einsatz von Übersetzungshilfen hemmt jede Kommunikation, unabhängig vom Milieu. Die Vorinstanz hat das Fehlen einer gemeinsamen Sprache der Beschwerdeführer und die damit verbundene erschwerte Kommunikation zu Recht als Indiz für eine Scheinehe gewertet.
3.3. Die Äusserungen der Beschwerdeführer zum Zeitpunkt und zu den Umständen des ersten Treffens, welches in Frankreich stattfand, und zweier Besuche im Kosovo stimmten nicht überein. Wie die Vorinstanz zutreffend erwog, lässt sich allein gestützt darauf noch nicht auf eine Scheinehe schliessen. Erschwerend kommt aber hinzu, dass die Beschwerdeführer auch nach einer (angeblichen) drei Jahre dauernden Beziehung und einer Heirat nur wenige Kenntnisse über den jeweiligen Partner und dessen Familie (Geburtsdatum, Namen der Schwiegereltern, Anzahl und Namen der Geschwister) vorweisen konnten. Die Vorinstanz wertete das Fehlen solcher Kenntnisse nicht nur als schwer verständlich, sondern wies auch darauf hin, dass die Beschwerdeführerin 2, auf die Unstimmigkeiten (etwa betreffend Anzahl und Geschlecht der Geschwister des Beschwerdeführers 1) angesprochen, ihre Aussage unter einem Vorwand korrigierte.
3.4. Auch in Bezug auf in der Schweiz lebende Cousins sowie weitere Verwandte und Freunde des Beschwerdeführers 1 machten die Beschwerdeführer widersprüchliche Aussagen. Hinsichtlich C._, den Ehemann von D._, gab die Beschwerdeführerin 2 an, er sei ein Cousin des Beschwerdeführers 1. Dieser selbst behauptete jedoch, mit C._ nicht verwandt zu sein, er kenne ihn nur flüchtig aus dem Kosovo. In Bezug auf E._, den Sohn von D._, gaben die Beschwerdeführer übereinstimmend an, er sei nicht der Freund der Beschwerdeführerin 2. Gemäss Bericht der Polizei Kanton Solothurn vom 5. Februar 2014, welcher D._ als Beschuldigte in einer polizeilichen Ermittlung betraf, war die Beschwerdeführerin 2 bei der Hausdurchsuchung vom 21. Januar 2014 als Freundin von E._ anwesend. Es ist nicht willkürlich, wenn die Vorinstanz der Behauptung der Beschwerdeführerin 2, ihre Beziehung zu E._ sei nur freundschaftlich, keinen Glauben schenkte.
3.5. Mit letzter Gewissheit aber bestätigte die Vorinstanz den Verdacht auf Scheinehe gestützt auf das Verhalten der Beschwerdeführerin 2 gegenüber der Sozialhilfebehörde. Gemäss Aktennotiz der Sozialen Dienste F._ vom 23. Dezember 2014 war die Beschwerdeführerin 2 zum Erstgespräch mit ihrem Freund E._ und dessen Mutter D._ erschienen und hatte angegeben, sie wohne bei diesen. Den Beschwerdeführer 1 habe sie nicht erwähnt, obwohl sie gemäss eigenen (späteren) Angaben seit 2012 mit ihm eine Beziehung geführt und ihn weniger als drei Monate nach dem Gespräch bei der Sozialhilfebehörde geheiratet habe. Zu einem weitereren Gespräch bei der gleichen Behörde vom 15. Januar 2016 sei sie - die Beschwerdeführerin 2 - wegen Krankheit nicht erschienen; statt dessen aber E._ und D._. Letztere habe gar gefragt, ob ein Teil der Kosten für die Verhütung der Beschwerdeführerin 2 von der Sozialhilfe übernommen werde. Die (zehn Monate zuvor geschlossene) Ehe mit dem Beschwerdeführer 1 sei weiterhin unerwähnt geblieben, ebenso der Umstand, dass dieser mittlerweile in derselben Wohnung lebte wie D._, E._ und die Beschwerdeführerin 2. Die zuständige Sozialarbeiterin sei immer davon ausgegangen, dass E._ und die Beschwerdeführerin 2 ein Paar seien. Die Beschwerdeführerin 2 habe nie gemeldet, dass sie verheiratet sei. Die Sozialhilfebehörde sei erst am 26. Januar 2016 durch den Anruf eines Sachbearbeiters der AHV-Zweigstelle auf die Heirat der Beschwerdeführerin 2 aufmerksam gemacht worden. In der Folge sei gegen die Beschwerdeführerin 2 und E._ Anzeige erstattet worden wegen Betrugs, Widerhandlung gegen das Sozialgesetz und Verletzung der Auskunftspflicht. Es könne als erstellt gelten, dass die schriftliche Angabe der Beschwerdeführerin 2 vom 8. September 2015, wonach sie nie eine Beziehung mit E._ geführt habe, falsch sei.
3.6. Diese Einschätzung ist weder willkürlich, noch vestösst sie auf andere Weise gegen Bundesrecht. Was die Beschwerdeführer dagegen vorbringen, überzeugt nicht. Es ist ihnen zwar zuzustimmen, dass der Beschwerdeführerin 2 nicht vorgeworfen werden darf, vor der Eheschliessung am 6. März 2015 ihren Ledignamen verwendet zu haben. Indessen verschwieg sie der Sozialhilfebehörde die Heirat auch dann noch, als diese längst erfolgt war. Dieses Verhalten zeigt, dass die Beschwerdeführer "Tisch und Bett" entgegen ihrer Behauptung nicht teilen, was ein sehr starkes Indiz für eine Scheinehe darstellt. Im Zusammenspiel mit den übrigen Indizien, insbesondere auch den erfolglosen Versuchen des Beschwerdeführers 1, in der Schweiz ein Aufenthaltsrecht zu erwirken, ergibt sich ohne weiteres der Schluss, dass die Beschwerdeführer die Ehe nur zum Schein eingegangen sind.
3.7. Unbegründet ist schliesslich die Rüge, die Vorinstanz habe von den Beschwerdeführern den unmöglichen Gegenbeweis verlangt, keine Scheinehe zu führen. Wenn es den Beschwerdeführern nicht gelungen ist, die zahlreichen Indizien, welche für eine Scheinehe sprechen, zu widerlegen, kann dies nicht der Vorinstanz angelastet werden. Vielmehr hatten und haben die Beschwerdeführer den einschlägigen Tatsachen, welche von der Vorinstanz willkürfrei festgestellt worden waren, nichts entgegenzusetzen. Von einer Verdrehung der Beweislast kann nicht gesprochen werden.
4.
Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Der Entscheid umfasst auch den Eventualantrag und die Subeventualanträge.
4.1. Bei diesem Ausgang des Verfahrens werden die unterliegenden Beschwerdeführer gemäss <ref-law> grundsätzlich kostenpflichtig; sie haben indessen um Gewährung der unentgeltlichen Rechtspflege ersucht. Es kann offen bleiben, ob auf das Gesuch eingetreten werden könnte, nachdem der Bedürftigkeitsnachweis nach Ablauf der Frist am 1. Dezember 2016 eingereicht worden ist:
Gemäss <ref-law> befreit das Bundesgericht eine Partei, die nicht über die erforderlichen Mittel verfügt, auf Antrag von der Bezahlung der Gerichtskosten und von der Sicherstellung der Parteientschädigung, sofern ihr Rechtsbegehren nicht aussichtslos erscheint. Wenn es zur Wahrung ihrer Rechte notwendig ist, bestellt das Bundesgericht der Partei einen Anwalt oder eine Anwältin (Art. 64 Abs. 2 erster Satz BGG). Praxisgemäss sind Prozessbegehren als aussichtslos anzusehen, bei denen die Gewinnaussichten beträchtlich geringer sind als die Verlustgefahren und die deshalb kaum als ernsthaft bezeichnet werden können; eine Partei soll einen Prozess, den sie auf eigene Rechnung und Gefahr nicht führen würde, nicht deshalb anstrengen können, weil er sie nichts kostet (<ref-ruling> E. 2.2.4; <ref-ruling> E. 2.3.1 S. 135 mit Hinweisen).
In Anbetracht der Sach- und Rechtslage waren dem Rechtsmittel keine realistischen Erfolgsaussichten beschieden. Die Beschwerde stützt sich fast ausschliesslich auf Sachverhaltsrügen, welche vom Bundesgericht mit eingeschränkter Kognition überprüft werden (<ref-law>). Dies musste den anwaltlich vertretenen Beschwerdeführern bekannt sein. Die Beschwerde erweist sich damit als aussichtslos. Das Gesuch um unentgeltliche Rechtspflege ist abzuweisen und die (umständehalber reduzierten) Gerichtskosten sind den Beschwerdeführern unter solidarischer Haftung aufzuerlegen (<ref-law>).
4.2. Ausgangsgemäss ist keine Parteientschädigung zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'000.-- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Solothurn und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 9. Mai 2017
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Die Gerichtsschreiberin: Genner