How can I remove a bad execution plan from Azure SQL Database?

Azure SQL now directly supports this

Azure SQL Database directly supports clearing the proc cache of the current user database without any hacks:

ALTER DATABASE SCOPED CONFIGURATION CLEAR PROCEDURE_CACHE;

Additional Information

The following script (by Shannon Gowen) can be used to watch the process step-by-step:

-- run this script against a user database, not master
-- count number of plans currently in cache
select count(*) from sys.dm_exec_cached_plans;

-- Executing this statement will clear the procedure cache in the current database, which means that all queries will have to recompile.
ALTER DATABASE SCOPED CONFIGURATION CLEAR PROCEDURE_CACHE;

-- count number of plans in cache now, after they were cleared from cache
select count(*) from sys.dm_exec_cached_plans;

-- list available plans
select * from sys.dm_exec_cached_plans;

There isn't an explicit way to do this today, but that isn't a permanent scenario (the DBCC command is still not supported, but read up on Query Store). Even when the schema change hit is acceptable, it may not be what you want, because it will invalidate all plans related to the underlying object, not just the bad one.

Not looking for credit for this, but building dynamic SQL to perform the same operation against multiple tables is pretty easy:

DECLARE @sql NVARCHAR(MAX) = N'';

SELECT @sql += N'ALTER TABLE '
  + QUOTENAME(SCHEMA_NAME([schema_id])) 
  + '.' + QUOTENAME(name) + ' ADD fake_column INT NULL;
  ALTER TABLE ' 
  + QUOTENAME(SCHEMA_NAME([schema_id]))
  + '.' + QUOTENAME(name) + ' DROP COLUMN fake_column;'
FROM sys.tables
--WHERE name IN, LIKE, etc.

PRINT @sql;

-- if the command > 8K, you can see the second chunk e.g.

PRINT SUBSTRING(@sql, 8001, 8000);

--EXEC sys.sp_executesql @sql;

(I wrote a tip about this "length of dynamic SQL" issue...)

Add a nullable column to the table then drop the column. That'll force SQL to flush the cache for that object.

As for doing all the tables, a cursor should do the trick. Just use a column name that'll never exist in any table like 'zzzzzz_go_away' or something.